[백준] 1018번: 체스판 다시 칠하기 - 파이썬(Python)

문제 링크

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

1018번: 체스판 다시 칠하기

 

문제

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

 

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

 

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

 

입력

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

 

출력

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

 

예제 입력 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

 

문제 풀이 및 코드

문제를 접근할 때 브루트 포스를 이용하여 풀이를 해보았으나 여러 번의 실패로 결국 다른 분들의 코드를 참고하여 해결하였습니다. 문제 해결 방법을 생각해내기가 꽤 어려운 문제였습니다.

 

가로 세로 길이를 나타내는 n, m을 입력받고, 전체 보드를 나타낼 리스트 borad, 결괏값을 나타낼 result 리스트를 선언하여 board 리스트에 전체 보드를 append() 함수를 통해 입력받습니다.

n, m = map(int, input().split())
board = []
result = []
 
for _ in range(n):
    board.append(input())

 

문제 규칙상 칠할 체스는 8x8 크기로 정해져 있으므로 n-7과 m-7 범위의 중첩 for문을 작성합니다. i, j는 체스판의 칠할 부분을 찾는 시작점을 나타냅니다.

n과 m에서 -7을 해주는 이유는 이 지점부터 8x8 크기의 체스판을 검사할 것이기 때문에 전체 보드판의 인덱스를 벗어나지 않기 위함입니다.

시작점이 바뀔 때마다 처음부터 칠해주기 위해 draw 변수를 선언하는데, 시작 지점이 검은색일 경우와 흰색일 경우를 대비하여 2개의 변수를 준비합니다.

for i in range(n-7):
    for j in range(m-7):
        draw1 = 0
        draw2 = 0

 

이후 시작점부터 8x8크기의 체스판을 탐색하여 칠할 개수를 찾아주기 위해 시작점인 i, j 지점부터 i+8, j+8 범위의 중첩 for문을 작성합니다.

조건문을 통해 board[a][b] 지점이 2로 나눈 나머지가 0일 때와 1일 때를 이용하여 언제 어느 색을 칠할지를 결정하여 다음과 같은 코드를 작성합니다.

만약 a + b를 2로 나눈 나머지가 0이라면, draw1은 검은색이 아닐 때 1을 더하여 색칠하고, draw2는 흰색이 아닐 때 1을 더하여 칠하는 것으로 시작점이 검은색일 때와 흰색일 때 두 가지 경우를 모두 해결합니다.

        for a in range(i, i+8):
            for b in range(j, j+8):
                if (a + b) % 2 == 0:
                    if board[a][b] != 'B':
                        draw1 += 1
                    if board[a][b] != 'W':
                        draw2 += 1
                else:
                    if board[a][b] != 'W':
                        draw1 += 1
                    if board[a][b] != 'B':
                        draw2 += 1
 
        result.append(draw1)
        result.append(draw2)
 
print(min(result))

8x8 크기의 체스판을 모두 칠했을 경우 결괏값 리스트에 추가하여 전체 보드에 대하여 칠할 횟수를 담은 뒤, min() 함수를 이용하여 가장 적은 횟수를 출력하면서 문제를 해결합니다. 

 

전체 코드

n, m = map(int, input().split())
board = []
result = []
 
for _ in range(n):
    board.append(input())
 
for i in range(n-7):
    for j in range(m-7):
        draw1 = 0
        draw2 = 0
 
        for a in range(i, i+8):
            for b in range(j, j+8):
                if (a + b) % 2 == 0:
                    if board[a][b] != 'B':
                        draw1 += 1
                    if board[a][b] != 'W':
                        draw2 += 1
                else:
                    if board[a][b] != 'W':
                        draw1 += 1
                    if board[a][b] != 'B':
                        draw2 += 1
 
        result.append(draw1)
        result.append(draw2)
 
print(min(result))

본 코드는 다른 분들의 코드를 참고하여 직접 작성한 것으로 더 나은 코드가 존재할 수 있으니 참고하시기 바랍니다.