1018번: 체스판 다시 칠하기

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

난이도: 실버 IV

해당 문제는 Python 3으로 풀이하였습니다.

우선 문제에서 입력으로 주어지는 N, M값을 각각 받아옵니다.

N, M = map(int, input().split())

그 뒤에 입력으로 주어지는 체스판 행렬을 받아옵니다. 이 때 계산의 편의를 위해 B는 1, W는 0이라는 정수 값으로 list에 저장하겠습니다.

arr = []

for i in range(0, N):
    row = list(input())
    for j in range(0, M):
        if row[j] == 'B':
            row[j] = 1
        else:
            row[j] = 0
    arr.append(row)

실제 문제에서는 8x8보다 큰 size의 보드가 주어지겠지만, 결국 정사각형을 칠하는 행위는 8x8 사이즈로 자른 후에 이루어질 것이므로 우선 8x8 사이즈의 단위 예시를 가지고 문제를 풀어봅니다.

문제에서 언급하였듯이,

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다.
구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고,
변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다.

따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다.
하지만 사실 어떤 경우를 두고 생각하더라도 이것이 크게 중요한 문제는 아닐 것입니다.

Idea 1.

체스판이기 때문에, 두 가지 case에 대해 모두 계산할 필요 없이, 한 가지의 case에 대해 "다시 칠해야 하는 정사각형의 수"를 계산한 후, 64 (8 x 8)에서 그 값을 빼 준다면 다른 한 가지 case에 대해서 계산한 값이 됩니다.
따라서, 이 두 값 중에 더 작은 값을 택하기만 하면 됩니다.

이 단위 예시에 대해 풀이하는 함수를 정의합니다.

def check(i, j, res):
    r = 0
    for row in range(0, 8):
        for col in range(0, 8):
            r += abs((row + col) % 2 - arr[i + row][j + col])
    if r < res:
        res = r
    if 64 - r < res:
        res = 64 - r
    return res

(row + col) % 2는 완전한 체스판 중에서 첫 번째 칸에 검정색이 칠해진 체스판의 (row, col) 위치에 칠해져야 할 값이고,
arr[i + row][j + col]은 단위 체스판에서 (row, col) 위치에 칠해진 값입니다.
이 두 값의 차를 모두 더한 값이 해당 단위 체스판에서 지민이가 다시 칠해야 하는 정사각형의 개수가 될 것입니다.

또한 Idea 1에서 언급하였듯이, r값이 32보다 크다면, 64에서 r값을 빼 주기만 하면 됩니다.
앞에서 언급하였듯이, r과 (64 - r) 중에서 더 작은 값을 택하기만 하면 되기 때문입니다.

이 함수를 모든 가능한 단위 체스판에 대해서 수행한 뒤, 최솟값을 최종적으로 출력하면 됩니다.
함수의 수행 횟수는 (N - 7) x (M - 7)회가 될 것입니다.

완성된 code

N, M = map(int, input().split())

res = 64
arr = []

def check(i, j, res):
    r = 0
    for row in range(0, 8):
        for col in range(0, 8):
            r += abs((row + col) % 2 - arr[i + row][j + col])
    if r < res:
        res = r
    if 64 - r < res:
        res = 64 - r
    return res

for i in range(0, N):
    row = list(input())
    for j in range(0, M):
        if row[j] == 'B':
            row[j] = 1
        else:
            row[j] = 0
    arr.append(row)
        
for i in range(0, N - 7):
    for j in range(0, M - 7):
        res = check(i, j, res)

print(res)

1018번: 체스판 다시 칠하기

Idea 1.

Idea 2.

완성된 code