개발/algorithm
[백준 1018번] 체스판 다시 칠하기 - python
zzi_on2
2022. 2. 13. 22:01
문제 링크
https://www.acmicpc.net/problem/1018
1018번: 체스판 다시 칠하기
첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
www.acmicpc.net
풀이
- 완전 탐색 문제
- answer : 다시 칠해야 하는 정사각형의 개수는 최대 64로 초기화
- 가능한 8 * 8 체스판에 대하여 칠해야 하는 체스판의 개수를 모두 확인한다.
- w_cnt = 0 : (0,0) 위치가 w로 시작할 때 다시 칠해야하는 판의 개수
- b_cnt = 0 : (0,0) 위치가 b로 시작할 때 다시 칠해야 하는 판의 개수
- graph[x][y]일 때 (x+y) % 2 가 0인 경우는 (0,0)에 칠한 체스판의 색과 같아야 하고
(x+y) % 2 가 1인 경우는 (0,0)에 칠한 체스판의 색과 달라야 한다.
- 칠해야되는 정사각형의 개수가 작은 것으로 answer 갱신
n, m = map(int,input().split())
graph = []
# 다시 칠해야 하는 정사각형의 개수는 최대 64
answer = 64
for _ in range(n):
graph.append(list(map(str,input())))
# 8 * 8 체스판을 만들 수 있는 모든 경우의 수에 대하여 탐색
for i in range(n-7):
for j in range(m-7):
w_cnt = 0 # (0,0) 위치가 w로 시작할 때 다시 칠해야하는 판의 개수
b_cnt = 0 # (0,0) 위치가 b로 시작할 때 다시 칠해야 하는 판의 개수
for x in range(8):
for y in range(8):
index = (x+y) % 2
if index == 0:
# (0,0) 위치가 w로 시작할 때 : w가 아니면 다시 칠해야 하므로 w_cnt + 1
if graph[i+x][j+y] != 'W':
w_cnt += 1
# (0,0) 위치가 b로 시작할 때 : b가 아니면 다시 칠해야 하므로 b_cnt + 1
if graph[i+x][j+y] != 'B':
b_cnt += 1
else:
# (0,0) 위치가 w로 시작할 때 : b가 아니면 다시 칠해야 하므로 w_cnt + 1
if graph[i+x][j+y] != 'B':
w_cnt += 1
# (0,0) 위치가 b로 시작할 때 : w가 아니면 다시 칠해야 하므로 b_cnt + 1
if graph[i+x][j+y] != 'W':
b_cnt += 1
# 칠해야 하는 체스판의 개수가 작은 것으로 갱신
answer = min(answer, b_cnt, w_cnt)
print(answer)