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

https://www.acmicpc.net/problem/1018

 

 

문제

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

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

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

 

풀이

실버4부터 벽이 느껴지는 ww

 

푸는 데 도움이 된 아이디어들

1. zip을 사용하여 체스판과 입력값을 비교해야겠다!

2. B로 시작하는 체스판에서의 틀린 개수 == 64 - (W로 시작하는 체스판에서의 틀린 개수)

n, m = map(int, input().split())
board = [list(input()) for _ in range(n)]
chess = ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W']

min_cnt = 64

for i in range(n - 7):
    for j in range(m - 7): #왼쪽끝점
        cnt = 0
        for k in range(i, i+8):
            for x, y in zip(board[k][j:j+8], chess):
                if k % 2 == 0 and x != y: cnt += 1
                if k % 2 == 1 and x == y: cnt += 1
        min_cnt = min(min_cnt, cnt, 64 - cnt)

print(min_cnt)

 

1. n, m을 입력받고 보드를 이차원 배열로 입력받는다.

2. 나올 수 있는 최댓값이 64이므로, min_cnt의 초깃값을 64로 설정한다.

3. 왼쪽 끝점이 될 수 있는 범위인 n-7, m-7에 대해 반복문을 돌린다.

4. 왼쪽 끝점에 대하여, k를 사용해 아래 8줄에 대한 검사를 실시한다.

5. zip을 사용하여 입력값과 체스판을 비교한다 (여기서 행 자리에 k 대신 i 써서 디버깅 엄청 고생함...)

6. 만약 짝수행이라면 BWBWBWBW와 다른값을 확인하고, 홀수행이라면 BWBWBWBW와 같은 값, 즉 WBWBWBWB와 다른값을 확인한다.

7. min을 사용하여 더 작은 값을 저장한다.

 

 

디버깅의 흔적 😹

 

샤라웃 투 아스트로피직순