[백준]1018번 체스판 다시 칠하기 - 완전 탐색

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

1018번: 체스판 다시 칠하기

 

 

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

chess = [[0] * m for i in range(n)]
for i in range(n):
    chess[i] = list(input())
change = 32  # 가장 최대로 많이 바꾸는 경우
for i in range(n):
    for j in range(m):
        if i + 8 <= n and j + 8 <= m:  # 인덱스 에러를 방지하기 위한 구문
            cnt1 = 0  # 시작을 W로 할 때 칠하는 숫자
            cnt2 = 0  # 시작을 B로 할 때 칠하는 숫자
            for x in range(8):
                for k in range(8):
                    if (x + k) % 2 == 0:  # 체스판의 짝수 번호 판별
                        if chess[x + i][k + j] != 'W':  # 시작을 W로 보았을 경우
                            cnt1 += 1
                        if chess[x + i][k + j] != 'B':  # 시작을 B로 보았을 경우
                            cnt2 += 1
                    else:  # 체스판이 홀수 번호 일때
                        if chess[x + i][k + j] != 'B':  # 시작을 W로 보았을 경우
                            cnt1 += 1
                        if chess[x + i][k + j] != 'W':  # 시작을 B로 보았을 경우
                            cnt2 += 1
            change = min(cnt1, cnt2, change)  # change, cnt1, cnt2 중 가장 적은수로 갱신
print(change)

 

코드 설명

체스판의 크기만큼 이중 반복문을 수행한다. 그 안에서  8*8 크기의 체스판을 구하기 위해 이중 반복문을 내부 반복문으로 수행한다.

체스판이 짝수인 경우와 홀수인 경우로 나눠서 생각한다. 그 안에서 시작이 W로 하는경우와 B로 하는 경우를 체크하며 바꿔 칠해야 할 체스판의 수를 체크한다.

 

Point : 체스판의 색을 가장 많이 칠하는 경우는 모두 W이거나 B인 경우, 즉 64의 절반인 32가 최댓값이 된다. change 횟수의 최댓값으로 초기화한다.

체스판의 짝수화 홀수를 통하여 색이 번갈아가며 진행되는지 판별한다. 그렇지 않은경우에는 카운트를 해준다.

또한 체스판의 시작이 W, B 로 총 2가지의 경우가 존재할 수 있으므로 cnt1, cnt2를 이용해 각각 카운트를 하여야 한다.

최종적으로 change와 cnt1(바꿔 칠해야 하는 값), cnt2 중 가장 적은 값을 선택해 정답을 출력한다.