BOJ 1018번 : 체스판 다시 칠하기

안녕하세요. 지난 포스팅의 BOJ 7568번 : 덩치에서는 브루트포스 알고리즘을 이용해서 간단하게 문제를 풀어보았습니다. 오늘은 살짝 꼬아서 어려운 문제를 풀어보도록 하죠.

 

 

완벽한 코딩은 존재하지 않습니다. 제가 제출한 코드 역시 마찬가지고 그저 참고만 해주시길 바랍니다. 

 

핵심 포인트

• 브루트포스

 

제출 코드

N, M = map(int, input().split())
board = [input() for _ in range(N)]
cnt_min = 9999
min_x, min_y = 9999, 9999
for x in range(0, N - 8 + 1) :
    for y in range(0, M - 8 + 1) :
        cnt_W, cnt_B = 0, 0
        for i in range(8) :
            for j in range(8) :
                    if (i + j) % 2 == 0 and board[x + i][y + j] != 'W' : cnt_W += 1
                    if (i + j) % 2 != 0 and board[x + i][y + j] != 'B' : cnt_W += 1
                    if (i + j) % 2 == 0 and board[x + i][y + j] != 'B' : cnt_B += 1
                    if (i + j) % 2 != 0 and board[x + i][y + j] != 'W' : cnt_B += 1
        if cnt_min > min(cnt_W, cnt_B) : 
            cnt_min = min(cnt_W, cnt_B)
            min_x = x
            min_y = y
print(cnt_min)

 

해설

제출 코드를 보시면 많이 복잡해보이지만 이해하시면 굉장히 단순한 코드라는 것을 알 수 있습니다. 먼저, 입력형식을 보도록 하죠. 이 문제는 첫번째 줄에 전체 보드의 가로, 세로 칸의 개수를 입력으로 받아줍니다. 다음 줄부터는 보드의 배치를 받죠. 이때, 저희가 구해야하는 것은 주어진 보드를 $8 \times 8$ 크기의 체스판으로 잘랐을 때 문제에서 제시하는 패턴을 만들기 위한 최소의 색칠 횟수를 출력해주어야 합니다.

 

WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

 

예를 들어 위의 보드판에서는 4번째 줄에서 BWBWBWBW가 되어야하지만 BWBBBWBW가 되기 때문에 한번 색을 바꾸어야하죠. 따라서, 이 경우에 출력은 1 입니다. 이 예시는 보드판의 크기가 $8 \times 8$로 한 번만 검사해도 색칠 최소횟수를 알 수 있습니다. 다만!! 여기서 주의해야할 점은 왼쪽 상단의 꼭 B나 W로 시작한다고 해서 해당 색을 기준으로 검사할 필요는 없습니다. 

 

BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBW

 

예를 들어 위의 보드판에서는 1번줄, 15번째 열에서 체스판을 잘랐다고 가정하겠습니다. 이 경우에는 잘린 체스판의 왼쪽 상단이 B이기 때문에 만약 B를 기준으로 색을 다시 칠하면 총 32번 칠해야합니다. 하지만, 만약 원래 W였다면 어떨까요? 그러면 총 31번 칠하면 되기 때문에 더 적은 횟수로 칠할 수 있습니다. 따라서, 이 경우에는 최소 색칠 횟수는 31번 입니다. 

 

이와 같이, 왼쪽 상단의 색깔을 고정해서 색칠 횟수를 확인하는 것이 아니라 하나의 체스판에 대해서 검은색인 경우와 흰색인 경우를 각각 한번씩 확인해주어야하는 것이죠. 이 과정을 이해하셨다면 코드를 쉽게 이해할 수 있습니다. 먼저, 첫번째 ~ 두번째 반복문은 $N \times M$ 크기의 보드판에서 $8 \times 8$ 크기의 체스판으로 자르는 과정을 보여줍니다. 시작 위치를 계속 변경하면서 색칠 횟수가 최소가 되는 체스판을 찾는 것이죠. 

 

그리고 지금까지 설명해드렸듯이 왼쪽 상단의 기준이 W와 B인 경우를 모두 확인하기 위해서 cnt_W와 cnt_B 변수를 선언해줍니다. 각각 W를 기준으로 했을 때, B를 기준으로 했을 때 색칠 횟수를 저장하게 됩니다. 

 

마지막 세번째 ~ 네번째 반복문에서는 잘려진 체스판을 쭉 훑으면서 W와 B를 기준으로 했을 때, 잘못 색칠된 칸의 개수를 세어줍니다. 이때, 조건은 다음과 같습니다. 

 

if i % 2 == 0 and j % 2 == 0 and board[x + i][y + j] != 'B' : cnt_W += 1
if i % 2 != 0 and j % 2 != 0 and board[x + i][y + j] != 'B' : cnt_W += 1
if i % 2 != 0 and j % 2 == 0 and board[x + i][y + j] != 'W' : cnt_W += 1
if i % 2 == 0 and j % 2 != 0 and board[x + i][y + j] != 'W' : cnt_W += 1

 

즉, 위 조건을 좀 더 단순화 시키면 아래와 같죠. 

 

if (i + j) % 2 == 0 and board[x + i][y + j] != 'W' : cnt_W += 1
if (i + j) % 2 != 0 and board[x + i][y + j] != 'B' : cnt_W += 1

 

짝수 + 짝수 = 홀수 + 홀수 = 짝수 그리고 짝수 + 홀수 = 홀수 + 짝수 = 홀수 임을 이용한 조건 축약입니다. 이 과정을 동일하게 cnt_B에도 적용해주면 되죠. 마지막으로 cnt_W와 cnt_B 중 더 작은 것을 찾은 뒤 cnt_min을 업데이트를 해주면 코드가 종료됩니다. 

 

참고자료 및 그림출처

백준 코딩 문제