[BOJ: 1018] - Python / 파이썬 - 체스판 다시 칠하기

o_jooon_·2024년 2월 6일

algorithm boj python

BOJ

목록 보기

30/49

서론

브루트포스 문제입니다.
실버 4 치고는 생각보다 어려운 문제여서 다른 분들의 풀이를 참고하였습니다.

난이도

실버 4

문제

조건

시간 제한	메모리 제한
2 초	128 MB

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

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

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

입력

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

출력

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

예시

예제 입력 1

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

예제 출력 1

예제 입력 2

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

예제 출력 2

풀이

색상을 어떻게 카운트 해줄 지가 핵심입니다.
r + c가 짝수인 경우와 홀수인 경우를 나눈 이유는 간단합니다.


(0, 0) - 흑	(0, 1) - 백	(0, 2) - 흑	(0, 3) - 백
(1, 0) - 백	(1, 1) - 흑	(1, 2) - 백	(1, 3) - 흑
(2, 0) - 흑	(2, 1) - 백	(2, 2) - 흑	(2, 3) - 백
(3, 0) - 백	(3, 1) - 흑	(3, 2) - 백	(3, 3) - 흑

체스판이 이런 식으로 구성이 되어있는 경우,
(0, 0), (0, 2), (1, 1) 등 처럼 서로 대각선에 있는 칸들의 색이 같기 때문입니다. -> r + c는 짝수
(1, 0), (0, 1), (3, 0) 등은 r+c가 짝수인 것들과 반대로 서로 대각선에 있는 칸들의 색이 같아집니다. -> r + c는 홀수

따라서 밑의 코드에 따르면,
보드판을 차례대로 8x8씩 탐색하면서 W와 B가 번갈아가며 존재하는 경우(cnt_a)와 B와 W가 번갈아가며 존재하는 경우(cnt_b) 중 더 적은 값을 찾고 값만 다시 칠하면 정상적인 체스판이 됩니다.
시작 지점이 B인지 W인지를 찾고 그에 맞는 대각선의 좌표를 구하여 카운트를 해주는 방법도 있지만, 그렇게 하면 코드가 훨씬 길어지기 때문에 이 방법이 훨씬 간편합니다.

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
board = [input().rstrip() for _ in range(n)]
ans = []	# 정답(최솟값)을 찾기 위한 배열

for i in range(n - 7):						# 8x8 배열을 탐색해야 하기 때문에 8칸 전까지 탐색
    for j in range(m - 7):
        cnt_a, cnt_b = 0, 0					# 다시 칠해야 할 색상 카운트(색상이 2개이기 떄문에 두 개)

        for r in range(i, i + 8):			# 현재 위치부터 8x8 배열 탐색
            for c in range(j, j + 8):
                if (r + c) % 2 == 0:		# r + c가 짝수인 경우
                    if board[r][c] == 'B':	# 짝수인 칸이 B라면
                        cnt_a += 1			# r + c가 짝수인 총 B의 갯수 카운트
                    else:					# 짝수인 칸이 W라면
                        cnt_b += 1			# r + c가 짝수인 총 W의 갯수 카운트
                else:						# r + c가 홀수인 경우
                    if board[r][c] == 'W':	# 홀수인 칸이 W라면
                        cnt_a += 1			# r + c가 홀수인 총 W의 갯수 카운트
                    else:					# 홀수인 칸이 B라면
                        cnt_b += 1			# r + c가 홀수인 총 B의 갯수 카운트
        
        ans.append(cnt_a)					# 정답 배열에 모두 넣어줌
        ans.append(cnt_b)

print(min(ans))								# 최솟값 출력