백준 1018번 풀이

문제

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

1018번: 체스판 다시 칠하기

보드에서 최소한으로 재도색하면서 체스판을 만들 수 있는 가짓수는?

 

Reference

https://bambbang00.tistory.com/43

[BAEKJOON]백준 1018번: 체스판 다시 칠하기 파이썬

 

풀이

체스판은 검흰검흰이거나 흰검흰검으로 반복된다. …앞에앞에 문제에 기물 주운 애랑 합치면 체스 세트 완성인데? 아무튼. 근데 이제 브루트 포스맛이면 8*8을 다 훑어보면서 체크하게 된다.

import sys
N, M = map(int, sys.stdin.readline().split())
board = []
cut_board = []
for _ in range(N):
    row = sys.stdin.readline().strip()
    board.append(row)
# 전체 보드 만들기

for m in range(N-7):
    for n in range(M-7):
        board_index_1 = 0
        board_index_2 = 0
        for o in range(m, m+8):
            for p in range(n, n+8):
                if (o + p) % 2 == 0:
                    if board[o][p] != 'W':
                        board_index_1 += 1
                    if board[o][p] != 'B': 
                        board_index_2 += 1
                else: 
                    if board[o][p] != 'B':
                        board_index_1 += 1
                    if board[o][p] != 'W':
                        board_index_2 += 1
        cut_board.append(min(board_index_1,board_index_2))

print(min(cut_board))

이게 전체 코드. 보드는 원래 보드(줍줍한 보드), 컷보드는 8*8로 자른 상태이다. 근데 뭔 for문이 이렇게 많냐고? 일단 위에 있는거 말고 요 두놈을 보자.

1. for m in range/for n in range
2. for o in range/for p in range

두 for문은 각각

1. 체스보드의 시작점(8*8로 자르는거지 주어진 게 8*8이 아님)
2. 시작점~시작점+8(range는 a 이상 b 미만)까지를 range로 해서 확인

이렇게 되어 있다. 위에도 썼지만 체스판이 8*8이니까 그걸로 잘라서 만드는거지 주어지는 판이 8*8이라는 법은 없다. 그럼 밑에 If가 네갈래인 이유는요?

if (o + p) % 2 == 0:
    if board[o][p] != 'W':
    	board_index_1 += 1
	if board[o][p] != 'B':
    	board_index_2 += 1
else :
    if board[o][p] != 'B':
    	board_index_1 += 1
	if board[o][p] != 'W':
    	board_index_2 += 1

체스판의 시작점이 검정색일때와 흰색일 때, 각각 인접해야 하는 색이 다르다. 즉 흰색 옆에는 검정, 검정 옆에는 흰색이 와야 해서 if가 저렇게 갈라졌다고 보면 된다.