문제

' 1018번 체스판 다시 칠하기 '
https://www.acmicpc.net/problem/1018

풀이

조건

• 첫째 줄에 N과 M이 주어진다. (N과 M은 8이상, 50이하의 자연수이다.)
• 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색, W는 흰색이다.
• 8 × 8 크기의 체스판으로 잘라낸 후에 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

풀이 순서

• 가로 N, 세로 M, 보드 배열을 입력값으로 받는다.
• 8 x 8 배열로 자를 수 있도록 범위를 지정해준다.
• 처음 점과 각 점과의 규칙을 적용하여 새로 칠해야 하는 수를 구한 뒤, 그 값이 최솟값이라면 출력할 수 있도록 한다.

Check point

• 기준으로 하는 처음 점도 색칠할 수 있다. 따라서 첫번째 점을 흰색으로 칠했을 때 규칙을 적용하여 새로 칠해야 하는 수를 구하고 검정색으로 칠했을 때 규칙을 적용한하여 새로 칠해야 하는 수를 구해서 최솟값을 구할 수 있도록 한다.
• 처음점과 같은 색이어야 하는 점들은 x, y 거리의 합이 짝수여야 한다. 예를들어 (0,0)이 흰색이라면 (1,1)도 흰색이어야 하고 (1,0)은 거리의 합이 홀수이므로 검정색이어야 한다.

코드

Python

N, M = map(int, input().split())
arr = [input() for _ in range(N)]
mn = 64  # 최소값 저장할 변수 (다시 칠해야 하는 최대값 8*8을 처음 지정)
for i in range(N + 1 - 8):  # 8*8 배열만큼 떼어내기
    for j in range(M + 1 - 8):
        tmp_black = 0  # 처음 시작점을 검정색으로 칠할 때 새로 칠해야 하는 경우
        tmp_white = 0  # 처음 시작점을 흰색으로 칠할 때 새로 칠해야 하는 경우
        for k in range(0, 8):
            for s in range(0, 8):
                if (k + s) % 2:  # 처음 시작점에서 거리의 합이 홀수인 경우 -> 시작점과 색깔이 달라야 한다.
                    if arr[i + k][j + s] == 'B':  # 처음 시작점이 검정색이고 거리의 합이 홀수인 지점이 검정색인 경우
                        tmp_black += 1  # 색칠해야 한다.
                    if arr[i + k][j + s] == 'W':
                        tmp_white += 1
                else:
                    if arr[i + k][j + s] != 'B':  # 처음 시작점에서 거리의 합이 짝수인 경우 -> 시작점과 색깔이 같아야 한다.
                        tmp_black += 1
                    if arr[i + k][j + s] != 'W':
                        tmp_white += 1
        if tmp_black < mn:  # 새로 칠해야 하는 수 중 가장 작은 값 출력하기
            mn = tmp_black
        if tmp_white < mn:
            mn = tmp_white
print(mn)