백준 1018 - 체스판 다시 칠하기

처음 든 생각

- 8*8 이라는 체스판의 크기를 일정하므로 시작점에 대한 좌표를 기준으로 가로 8개, 세로 8개를 세면 되겠다.

- 다시 칠해야하는 개수는 정답 후보군이 2개 밖에 없으므로 정답을 하드코딩하여 비교해준다.

 

나의 답

import sys
input=  sys.stdin.readline
N, M = map(int,input().split())

ans1 = [
    ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
    ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
    ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
    ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
    ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
    ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
    ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
    ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
]
ans2 = [
    ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
    ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
    ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
    ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
    ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
    ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
    ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
    ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
]
arr = [ list(input()) for _ in range(N) ]

def checkChess(x,y):
    cnt1 = 0
    cnt2 = 0
    for i in range(8):
        for j in range(8):
            if arr[x+i][y+j] != ans1[i][j]:
                cnt1 += 1
            if arr[x+i][y+j] != ans2[i][j]:
                cnt2 += 1
    return min(cnt1,cnt2)

result = 1000000000
for i in range(N-7):
    for j in range(M-7):
        result = min(result,checkChess(i,j))

print(result)

 

두 개의 정답 체스판을 2차원 행렬로 선언해주었다.

 

다시 칠해야하는 정사각형의 개수를 구하기 위한 함수를 따로 만들었다.

1번 정답, 2번 정답과 비교하여 각각의 수정 개수를 비교하여 최소값을 리턴하게 된다.

 

그 다음 모든 가능 시작 꼭지점에 대하여 결과를 확인하여 최솟값을 도출하면 된다.

시간 복잡도가 괜찮을지 고민이 잠깐 됐는데 50보다 작거나 같은 자연수 이기에 어림잡아 최대 연산 횟수가 50^2 * 8^2  = 160,000이므로 무리 없다고 생각하였다.