📜문제 설명

문제 바로가기

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

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

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

📍입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

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

📍출력

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

1

12

---

📄문제 해결

📝내가 푼 코드

❎ 1차 시도

# 8*8 배열에서 W의 개수를 세고 64를 뺀 절댓값을 반환 = W와 B 개수 차이
def get_wb_diff(arr):
    cnt = 0
    for a in arr:
        cnt += a.count("W")
    
    return abs(32-cnt)

N, M = map(int, input().split(' '))
board = [list(input()) for _ in range(N)]
diffs = []

for i in range(0, N-7): # i ~ i+7 (i:i+8)
    for j in range(0, M-7): # j ~ j+7 (j:j+8)
        arr = []
        for k in range(8):
            arr.append(board[i+k][j:j+8])
        print_arr(arr)
        diff = get_wb_diff(arr)
        diffs.append(diff)
        if diff == 0: 
            break
        
print(min(diffs))

1차 시도는 단순히 2차원 배열을 모두 탐색하면서 8*8로 자른 체스판(배열) 안의 W와 B의 개수 차이를 구하고, 그 결과를 곧 다시 칠해야하는 칸으로 출력하게 했다. 하지만 이 방식은 여러 문제가 있다. 만약, 잘못 칠해져서 새로 W와 B로 칠해야 하는 칸의 개수가 각각 같다면?

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWWWB
BWBWBWBW

위 예제는 겉으로 보기에, 그리고 단순이 개수만 세면 B와 W의 개수가 같아 큰 문제가 없어 보이지만, 네 번째 줄에 BBB, 그리고 일곱 번째 줄에 WWW가 연속되는 것을 확인할 수 있다. 따라서 개수를 세 비교하는 방식은 의미가 없어진다.

따라서, 8*8로 자른 체스판 배열도 안에서 올바르게 색칠되어 있는지 탐색이 필요하다. 이는 어떻게 할 수 있을까?

✅ 2차 시도

# Python3 메모리: 32412KB, 시간: 64ms

N, M = map(int, input().split(' '))
board = [list(input()) for _ in range(N)]

w1 = ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B']
w2 = ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W']

min_cnt = None
for i in range(0, N-7): # 시작점: i ~ i+7 (i:i+8)
    for j in range(0, M-7): # 시작점: j ~ j+7 (j:j+8)
        cnt = 0
        for x in range(8):
            for y in range(8):
                if x%2: # 홀수
                    if board[i+x][j+y] != w2[y]:
                        cnt += 1
                else: # 짝수
                    if board[i+x][j+y] != w1[y]:
                        cnt += 1

        cnt = min(cnt, 64-cnt) # 블랙 체스판 vs 화이트 체스판 중 비용이 적은 것

        if min_cnt is None or min_cnt > cnt: # 최솟값 갱신
            min_cnt = cnt

print(min_cnt)

1차 시도를 하고 며칠 뒤, 다시 문제와 멘토님이 알려주신 힌트를 다시 되새기면서 로직을 생각했다.

가장 문제는 어떻게 색칠해야할 칸을 찾을 것인가? 였다. 내가 풀면서도 가장 아이디어가 떠오르지 않았던 점이었는데, 멘토님께서 알려주신 힌트에서 화이트 체스판과 블랙 체스판을 나눠 생각하다보니 결국 화이트 체스판과 블랙 체스판 중에서 하나의 경우만 구하면 되기 때문에(이유는 후술하겠다.), 칠해야할 결과는 알고 있는 것과 마찬가지라는 생각이 들었다. 우리가 보통 아는 체스판, 흰색과 검은색이 교차하는 그 체스판으로 칠하면 되기 때문에 나는 인덱스를 기준으로 화이트 체스판의 홀수 행과 짝수 행의 정답을 변수에 저장한 뒤 주어진 체스판과 다른 경우를 카운트하도록 했다.

화이트 체스판과 블랙 체스판 중 하나의 경우만 구해도 되는 이유, 그리고 이 문제를 풀 때 시간복잡도를 줄일 수 있는 포인트는 화이트 체스판을 만들 때의 비용과 블랙 체스판을 만들 때의 비용은 서로의 값을 활용해 구할 수 있다는 것이다.

예를 들어 상태가 아래와 같을 때, 블랙 체스판을 만들기 위해 다시 칠할 칸은 없으므로 최소 비은 0, 화이트 체스판을 만들기 위해서는 모든 칸을 다시 칠해야하기 때문에 최소 비용은 4이다.

B W
W B

다른 경우, 이때 블랙 체스판을 만들기 위해서는 1칸만 칠하면 되므로 최소 비용은 1, 화이트 체스판을 만들기 위해서는 3칸을 칠해야 하므로 최소 비용은 3이다.

W W
W B

이처럼 체스판의 전체 칸 개수에서 블랙 체스판을 만들기 위한 최소 비용을 뺄 경우, 화이트 체스판을 만들기 위한 최소 비용을 구할 수 있다. 이를 활용해 화이트 체스판의 최소 비용만을 구해 블랙 체스판의 최소 비용을 구해 두 결과를 비교해 최솟값을 갱신하도록 했다.

---

🤔느낀점

월요일에 풀 때는 정말 막막했는데, 며칠이 지난 뒤에 멘토님의 힌트와 코드를 조금씩 보니 아, 이렇게 풀면 되는구나 하고 빠르게 문제를 풀 수 있었다. 풀고나니 정말 쉽게 풀 수 있는 문제였는데 너무 복잡하고 어렵게 생각했었던 것 같다는 생각이 든다.