백준 : 체스판 다시 칠하기 - 1018

출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

예제 입력 1 

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

예제 출력 1 

1

예제 입력 2 

10 13
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
WWWWWWWWWWBWB
WWWWWWWWWWBWB

예제 출력 2 

12

예제 입력 3 

8 8
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB

예제 출력 3 

0

예제 입력 4 

9 23
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBW

예제 출력 4 

31

예제 입력 5 

10 10
BBBBBBBBBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBBBBBBBBB

예제 출력 5 

0

예제 입력 6 

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWWWB
BWBWBWBW

예제 출력 6 

2

예제 입력 7 

11 12
BWWBWWBWWBWW
BWWBWBBWWBWW
WBWWBWBBWWBW
BWWBWBBWWBWW
WBWWBWBBWWBW
BWWBWBBWWBWW
WBWWBWBBWWBW
BWWBWBWWWBWW
WBWWBWBBWWBW
BWWBWBBWWBWW
WBWWBWBBWWBW

예제 출력 7 

15

 

이 문제는 솔직하게 곧바로 문제를 어떻게 풀지 생각나지 못했다. 어떻게 해야할지 고민이 많이 된 문제였다. 일단 패턴으로는 8X8의 정사각형이 있으며, B로 시작하는 패턴, W로 시작하는 패턴 2가지가 존재한다. 

 

import sys

def solve():
    N, M = map(int, sys.stdin.readline().split())
    board = []
    for _ in range(N):
        board.append(sys.stdin.readline().strip())

    min_changes = float('inf')  # 최소 변경 횟수를 저장할 변수, 무한대로 초기화

초기에는 입력값과 답을 찾기 전에 최소 칠하기 횟루르 저장할 변수를 초기화 시켰다.

 

for i in range(N - 7):
        for j in range(M - 7):
            count_w_start = 0
            count_b_start = 0

            for x in range(i, i + 8):
                for y in range(j, j + 8):
                    if (x + y) % 2 == 0:
                        if board[x][y] != 'W':
                            count_w_start += 1
                        if board[x][y] != 'B':
                            count_b_start += 1
                    else:
                        if board[x][y] != 'B':
                            count_w_start += 1
                        if board[x][y] != 'W':
                            count_b_start += 1

            min_changes = min(min_changes, count_w_start, count_b_start)

여기가 중요한데 이중 반복문은 모든 가능한 8X8 보드의 시작점을 i,j 로 지정하여 시작하고 N-7, M-7로 하는 이유는 보드 범위가 벗어나지 않도록 하기 위함이다.  예를 들어, 10x10 보드에서 8x8 보드는 행의 경우 0, 1, 2 (총 3개), 열의 경우 0, 1, 2 (총 3개)의 시작점을 가질 수 있있다. range(10-7)은 range(3)이므로 0, 1, 2가 된다.

그렇게 두번째 이중 반복문은 현재 선택된 보드 내부의 모든 칸을 탐색하도록 하고, if (x + y) % 2 == 0:: 이 조건은 (x,y) 칸이 시작점 (i,j)와 동일한 색상이어야 하는 위치인지 판별하도록 한다. 게다가 홀수라면 시작점과 당연히 다른 색상이어야 한다.

min_changes = min(min_changes, count_w_start, count_b_start): 한 8x8 보드에 대한 계산이 끝나면, W 시작 횟수와 B 시작 횟수 중 더 작은 값을 찾아 현재의 min_changes와 비교하여 최소값을 갱신하도록 한다.

 

이 문제는 스스로 다 풀지 못했고, 다른 분들의 코드를 참고하여 문제를 해결하였다. 

https://ittrue.tistory.com/60, 

https://dev-nicitis.tistory.com/62 (특히 이 분은 참고하는 것보다 색다른 접근법으로 놀랐다.)