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

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

 

입출력 예시

예시가 많아서 하나만 가져왔다 🙂

 

풀이

문제 이해하는 시간은 그렇게 오래 걸리지 않았는데 내가 생각한대로 구현하려고 했더니 주먹구구식으로 푸는 느낌이 들어(이해하고 에러 고치는 것 X 어? 인덱스 이렇게 넣으니까 에러나네 순서 바꿔봐야지 O 이런 느낌) 여러 고수분들의 잘 정제된 코드를 참고했다. 구현 문제를 등한시하지 말자는 교훈을 얻게 되었다.

 

# Silver 4

import sys

rows, cols = map(int, sys.stdin.readline().split())

board = [sys.stdin.readline().rstrip() for _ in range(rows)]

result = []

for row in range(rows-7):
    for col in range(cols-7):
        cnt1, cnt2 = 0, 0
        
        # 나눠진 정사각형별로 확인
        for r in range(row, row+8):
            for c in range(col, col+8):
                if (r+c)%2 == 0:
                    if board[r][c] != 'W':
                        cnt1 += 1
                    if board[r][c] != 'B':
                        cnt2 += 1
                else:
                    if board[r][c] != 'B':
                        cnt1 += 1
                    if board[r][c] != 'W':
                        cnt2 += 1
                        
        result.append(cnt1)
        result.append(cnt2)

print(min(result))

 

통과된 코드들을 참고하면서 한 가지 궁금증이 있었고 스스로 궁금증에 대한 답을 생각해보았다.

 

🧐 Q. 시작점 확인

나눠진 정사각형별로 맨 왼쪽 위 칸이 무슨 색인지 확인을 해야 한다고 생각했기 때문에 처음에는 거기에 맞춰서 코드를 짰다.

 

1) 맨 왼쪽 위 칸이 검은색일 때

2) 맨 왼쪽 위 칸이 흰색일 때

 

두 가지 경우로 나눠 코드를 작성하려고 했는데 조건문과 중복되는 코드가 많아서 이렇게 하는 게 맞나 싶은 생각이 들었다. 그런데 다른 분들의 코드는 시작점의 색을 따로 체크하지 않고 바로 cnt 변수에 값을 더해주는 조건문부터 시작하는 것이었음!

 

🤓 A. line 18, 23

Line 18과 23의 조건문이 해답이었다.

 

문제에서 체스판은 W B W B ... / B W B W ... 형태로 칠해져야 한다고 했기 때문에 r행의 짝수 인덱스들은 무조건 시작점과 색이 같아야 한다. 즉 cnt1 변수는 시작점이 'W'일 때 다시 칠해야 하는 칸의 개수이고 cnt2 변수는 시작점이 'B'일 때 다시 칠해야 하는 칸의 개수이다.

 

cn1, cnt2 변수의 역할에 대해 인지한 상태로 line 23을 보면 r행의 홀수 인덱스들은 무조건 시작점과 색이 달라야 하기 때문에 line 18의 조건문과 'B', 'W'의 위치가 바뀌게 된다.