Search

BOJ 1018 체스판 다시 칠하기

URL
태그
브루트포스 알고리즘

문제 설명

•
N×M N \times M 보드판에 대해, 8×8 8 \times 8 체스판을 만드는 최소 색칠 횟수
◦
체스판은 검은색과 흰색이 번갈아가면서 칠해져 있어야 한다.

예제 입력/출력

•
입력1
10 13 BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB WWWWWWWWWWBWB WWWWWWWWWWBWB
Plain Text
복사
•
출력1
12
Plain Text
복사

제약 조건

•
8≤N,M≤508 ≤ N, M ≤ 50

문제 풀이

•
모든 경우에 대해 살펴보는 브루트 포스적인 방식 - O(2×NM×64)O(2 \times NM \times 64)
◦
최대 연산 횟수는 32만회

풀이 코드

def sum_arr(chess, sy, sx): global board sum = 0 for i in range(8): for j in range(8): sum += board[sy + i][sx + j] != chess[i][j] return sum # Init chess1 = [['' for _ in range(8)] for _ in range(8)] chess2 = [['' for _ in range(8)] for _ in range(8)] for i in range(8): for j in range(8): chess1[i][j] = 'B' if (i + j) % 2 == 0 else 'W' chess2[i][j] = 'W' if (i + j) % 2 == 0 else 'B' # Input N, M = map(int, input().split()) board = [input() for _ in range(N)] # Solve best = int(1e9) for y in range(N): for x in range(M): if (y + 7 >= N) or (x + 7 >= M): continue case1 = sum_arr(chess1, y, x) case2 = sum_arr(chess2, y, x) best = min(best, case1, case2) print(best)
Python
복사