https://www.acmicpc.net/problem/1018
1018번: 체스판 다시 칠하기
첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
www.acmicpc.net
처음에는 그래프 문제라고 판단을 하여 BFS로 이웃한 사각형 같을 경우 다른 것으로 바꿔버리는 방식으로 풀었다.
그러나 예외 사항이 너무 많아서 다른 방식을 고민해보았다.
생각을 해보다가 간단한 방식이 떠올랐다.
8x8 체스판의 경우 무조건 두 가지 경우의 수만 존재한다.
<첫 번째>
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
<두 번째>
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
그리고 8x8의 임의의 보드가 주어졌을 때 모든 칸을 비교해가면서 서로 다른 칸이 몇 개인지 알아내기만 하면 된다.
첫 번째와 두 번째 경우와 비교하여 더 작은 값이 정답이 된다.
그러나 첫 번째와 두 번째를 전부 비교할 필요는 없다.
첫 번째만 선택하여 다른 칸의 개수를 구하고 나면 64에서 해당 값을 빼면 두 번째와 보드의 서로 다른 칸의 개수가 나오게 된다.
그래서 비교를 위한 체스판을 이중 리스트로 만든다.
chess=[['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W']]
주어지는 보드 판은 8x8 크기보다 큰 것도 오기 때문에 반복문으로 8x8 크기의 부분 보드판을 전부 구해서 비교해야한다.
예를 들어 10x10 보드판이 온다면
.
.
.
위와 같이 8x8 보드판을 모두 구해서 비교하는 것이다.
<전체 코드>
import sys
chess=[['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W']]
n, m = map(int, sys.stdin.readline().split())
res=n*m
inp = []
for _ in range(n):
inp.append(list(sys.stdin.readline().strip('\n')))
def ch(x, y):
cnt=0
for i in range(8):
for j in range(8):
if chess[i][j]==inp[x+i][y+j]:
cnt+=1
return min(cnt, 64-cnt)
for i in range(n-7):
for j in range(m-7):
res=min(res, ch(i, j))
print(res)이렇게 모든 경우를 구해서 최소값을 구하면 된다.
댓글