[브루트 포스 / Python] BOJ 1018 - 체스판 다시 칠하기

www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

---

해결 방법

8X8 체스판의 모든 좌표를 탐색해서 해당 위치에 W(혹은 B)가 없는 경우 이를 count 한다.

해결 과정

8X8보다 큰 체스판이 입력된 경우 시작 지점을 나눈다.

ex)

9X8 > [0][0]과 [1][0] : 2개의 시작 지점

10X13 > [0][0], [0][1], [0][2], [0][3], [0][4], [0][5], [1][0], ... [2][0], ... , [2][5] : 18개의 시작 지점

 

각 시작 지점에 따라 8X8의 체스판을 탐색한다.

탐색이 종료되면 count 한 값을 새로운 배열에 저장한다.

모든 과정이 종료되면 min 함수를 이용하여 최소값을 출력한다.

 

 

최종 코드는

 

def main():
    n, m = map(int, input().split())
    chess = [[0] for _ in range(n)]
    result = []
    
    for i in range(n):
        chess[i] = list(input())
        
    for i in range(n-7):
        for j in range(m-7):
            startW = 0
            startB = 0
            for k in range(i, i+8):
                for l in range(j, j+8):
                    if (k+l)%2 == 0:    # (0,0), (0,2), (2,0), ...
                        if chess[k][l] != "W":
                            startW += 1
                        if chess[k][l] != "B":
                            startB += 1
                    else:
                        if chess[k][l] != "B":
                            startW += 1
                        if chess[k][l] != "W":
                            startB += 1
                        
            result.append(startW)
            result.append(startB)
        
    print(min(result))
    
if __name__ == "__main__":
    main()

 

startW는 [0][0], 즉 시작 지점이 W일 때 칠해야하는 색깔이다. (startB는 시작 지점이 B일 때)