백준 1018) 체스판 다시 칠하기[Python]

 

 

체스판 다시 칠하기 문제는 brute force 의 시작을 알려주는 문제인 것 같다.

 

---

 

문제정의

 

1. N*M 개의 정사각형으로 이루어진 보드가 주어진다.

2. 이 중에서 8*8 의 크기를 가진 체스판을 만드려고 한다.

3. 체스판은 한 정사각형이 검은색이라면 다른 정사각형은 흰색이 나와야한다.

4. N*M 개 중에서 임의로 8*8 크기의 보드를 꺼냈으니 (3) 을 어길 수 있다.

5. 그렇기 때문에 제대로 체스 판을 만들기 위해서 다시 색을 칠해야 하는 수를 구하는 프로그램을 작성해라.

 

---

아이디어

1. 체스판의 8*8 보드는 [0][0] 위치의 색이 검정색이거나 흰색인 경우 두가지이다. 따라서 아래처럼 이거나 아래의 색을 바꿔 [0][0] 이 흰색인 경우만 가능하다. 

B	W	B	W	B	W	B	W
W	B	W	B	W	B	W	B
B	W	B	W	B	W	B	W
W	B	W	B	W	B	W	B
B	W	B	W	B	W	B	W
W	B	W	B	W	B	W	B
B	W	B	W	B	W	B	W
W	B	W	B	W	B	W	B

 

2. 그렇다면 (1) 의 전제를 가지고  전체 M*N 의 보드의 [0][0] 부터 8by8 의 윈도우를 만들며 새로 색칠해야 하는 수를 계산하면 된다.

3. 새로 색칠해야 하는 수는 레퍼런스로 갖고 있는 보드와 얼마나 다른 색을 갖고 있는지를 확인하면 된다. 

    - (1) 에 레퍼런스로 갖고 있는 보드는 두가지 경우의 수만 가능하기 때문에 

for i in range(0,8):
	for j in range(0,8):

        if ref_board[i][j] == window_board[window_start_index+i][window_start_index+j]:
            cnt+=1
            
return min(cnt,64-cnt)

 

의 의사코드 정도로 해결 할 수 있을 것이다. 

 

---

 

전체코드

import sys
ref_board=[['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
       ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
       ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
       ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
       ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
       ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
       ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
       ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W']]
n, m = map(int, sys.stdin.readline().split())


whole_board = []

res=n*m

for _ in range(n):
    whole_board.append(list(sys.stdin.readline().strip('\n')))
    
def window(x, y):
    cnt=0
    for i in range(8):
        for j in range(8):
            if chess[i][j]==whole_board[x+i][y+j]:
                cnt+=1
    return min(cnt, 64-cnt)
for i in range(n-7):
    for j in range(m-7):
        res=min(res, window(i, j))
print(res)