[Python] 1018 - 체스판 다시 칠하기 (실버4)

1. 문제 설명

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

1018번: 체스판 다시 칠하기

기억은 안 나지만 당시에 나름 어려웠던 것 같다.

실버 단계가 어려운 이유는 내가 너무 문제를 복잡하게 이해하려 하기 때문이지 싶다.

때론 단순무식한 방법들이 효율적인 해결책이 될 수 있다. 특히 실버 단계에선 대부분 그렇다.

물론 그 중에서 종종 특출난 아이디어를 필요로 하는 함정 문제들이 있긴 하지만 :)

 

---

2. 아이디어

어디나 상관없이 새로 칠해야 하는 경우가 가장 작은 8x8범위만 찾아내면 된다.

즉, 8x8범위만큼 탐색을 하는 과정을 가능한만큼 가로, 세로로 이동시키면서 반복하면 된다.

 

현재 좌표 y + x를 2로 나누었을 때 나머지가 짝수인 경우에 해당 위치가 W로 시작한다면,

나머지가 홀수인 경우엔 B가 들어오는 게 현재 내가 바라는 이상적인 체스판이 된다.

반대로 y + x를 2로 나누었을 때 나머지가 짝수인 자리에 B가 시작하는 경우도 고려한다.

이런 경우에는 나머지가 홀수인 경우 W가 들어와야 이상적이다.

 

한번에 모든 경우를 탐색하고 그 중에서 새로 칠해야 되는 경우가 더 적은 케이스를 리스트에 append한다.

그리고 그렇게 모은 결과에서 또 가장 작은 값을 print하면 통과~

 

---

3. 코드

def main():
    row, col = map(int, input().split())
    board = [[0]*col for _ in range(row)]
    cnt = []

    for i in range(0, row):
        board[i] = input()
    for i in range(0, row - 7):
        for j in range(0, col - 7):
            idx_w = 0
            idx_b = 0
            for min_i in range(i, i + 8):
                for min_j in range(j, j + 8):
                    if (min_i + min_j) % 2 == 0:
                        if board[min_i][min_j] != 'W': # white 시작하는 경우
                            idx_w += 1
                        else:
                            idx_b += 1
                    else:
                        if board[min_i][min_j] != 'B':
                            idx_w += 1
                        else:
                            idx_b += 1
            cnt.append(min(idx_w, idx_b))
    print(min(cnt))

main()