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

Python3

문제

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

키워드

• 브루트포스

문제 풀이

문제 요구사항

• M×N 크기의 보드
• 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.
• 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다
• 따라서 체스판을 색칠하는 경우는 두 가지 뿐이다. (하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.)
• 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램
• N개의 줄에는 보드의 각 행의 상태가 주어진다. (B는 검은색이며, W는 흰색)

변수 및 함수 설명

• n : 세로 길이
• m : 가로 길이 (N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수)

• board : 체스판
• ans : 색칠해야 하는 개수 배열
• draw1, draw2 : 흰색으로 시작하는 판이 색칠해야 하는 양, 검정색으로 시작하는 판의 색칠해야 하는 양

풀이

(입력 및 선언)

• 보드판 크기 입력받기
• 체스판 입력 받기

(색칠해야 하는 칸 찾기)

• 8x8 크기의 체스판을 만들어야 하기 때문에 n-7 x m-7 까지 반복한다. (시작점을 찾는 반복문)
• draw1, draw2를 초기화시킨다.
• 8x8 내부 체스판 색깔을 탐색한다.
• 문제 조건에서 시작하는 칸은 흰색, 검정색만 가능하다고 하였으므로 두 가지를 동시에 카운트할 것이다.
• board[a][b] 라고 가정할 때, a와 b를 더했을 때 짝수인 경우와 홀수인 경우를 나눈다.
• a+b의 위치는 모두 하나로 통일된 값이어야 한다.

  WBWBWBWB
  BWBWBWBW
  WBWBWBWB
  BWBBBWBW
  WBWBWBWB
  BWBWBWBW
  WBWBWBWB
  BWBWBWBW
  WBWBWBWB
  BWBWBWBW

bold된 부분의 값이 모두 a+b가 짝수인 부분이다.

• 해당 값이 W면 draw1에 1씩 카운트해서 올리고, B이면 draw2에 1을 증가시킨다.
• a+b가 홀수인 칸은 반대로 B일 때 draw1, W일 때 draw2를 한다.
• 이렇게 계산하면 흰검이 반복되도록 색칠해야 하는 양이 나온다.
• 이 값을 ans 배열에 넣고 최솟값을 출력하면 된다.

최종 코드

n, m = map(int, input().split())

board = []
ans = []

for _ in range(n) :
    board.append(list(map(str, 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] == 'W' :
                        draw1 += 1
                    elif board[a][b] == 'B' :
                        draw2 += 1
                else :
                    if board[a][b] == 'B' :
                        draw1 += 1
                    elif board[a][b] == 'W' :
                        draw2 += 1
                    
        ans.append(draw1)
        ans.append(draw2)
    
print(min(ans))