백준 알고리즘(파이썬) - 1018번

체스판 다시 칠하기

https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

다시 칠하기 위한 칸 수를 구하는데 쉽게 구하는 방법을 생각해봤지만 결국 모든 경우의 수를 확인하는 쪽으로 코드를 작성했다.

이런식으로 하나하나 옮겨가며 확인해야 한다. 여기에서 배열을 확인하는 시작점을 (a, b)라고 설정하고, 아래의 코드를 작성했다.

N, M = map(int, input().split())
board = []
for _ in range(N):
    board.append(input())
chess = ['WBWBWBWB', 'BWBWBWBW']
count = []
for a in range(N-7):
    for b in range(M-7):
        chess_W = 0
        chess_B = 0
        for i in range(a, a+8):
            for j in range(b, b+8):
                if board[i][j] != chess[i%2][j-b]: chess_W += 1
                if board[i][j] != chess[(i+1)%2][j-b]: chess_B += 1
        count.append(chess_W)
        count.append(chess_B)
print(min(count))

N줄 M칸의 보드를 입력받아 board에 저장한다.

chess는 체스판과 비교하기 위한 정보이다.

비교하는 8*8 시작점을 (a, b)로 옮겨가며 확인하도록 한다. 범위는 range(N-7)로 설정해야 모든 경우의 수를 확인할 수 있다.

 

i와 j는 8*8칸 안에서 chess의 정보와 비교하기위한 index이다.

if board[i][j] != chess[i%2][j-b]: chess_W += 1 에서는 맨 왼쪽 위칸이 W로 시작하는 경우를 확인하고,

if board[i][j] != chess[(i+1)%2][j-b]: chess_B += 1 에서는 맨 왼쪽 위칸이 B로 시작하는 경우를 확인한다.

j-b를 하지 않으면 chess의 데이터는 index가 7까지밖에 없으므로 index error를 일으킨다. j-b를 통해 chess의 string을 0부터 7번째까지 확인하도록 한다.

 

8*8 배열을 다 돌고 나면, count에 칠하는 횟수를 입력해주고 모든 경우를 탐색한 후에 min(count)로 가장 작은 값을 출력하도록 한다.