1018번: 체스판 다시 칠하기
https://www.acmicpc.net/problem/1018
문제 정의
M*N 크기의 보드에서 8*8 크기의 체스판을 만들려고 한다.
체스판은 검은색/ 흰색이 번갈아 칠해져있어야 하는데, 보드는 그렇지 않다.
보드를 8*8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해서 체스판을 만들 때, 칠해야 하는 최소 정사각형 개수를 구하면 된다.
접근 방법
N과 M의 범위가 50보다 작거나 같다고 해서 모든 원소는 최대 2500개이고, 그 중에서도 8*8 크기의 체스판이면 64개로 4중 for문을 돌아도 시간 초과는 나지 않는다.
따라서 완전 탐색으로 접근했다.
시작점이 되는 원소를 기준으로 8*8 크기의 체스판을 만들고, 그 체스판 원소 중 색칠을 다시 해야 하는 부분을 카운트 하기로 했다.
문제 해설
- board에 주어진 입력을 받는다.
- 시작점을 기준으로 8*8 크기의 체스판을 떼와야 하는데, 이 때 보드의 범위를 벗어나면 인덱스에러가 발생하므로, for문의 범위를 잘 지정해준다.
- N-8 번째 원소~8칸을 포함하면, 딱 N이 되므로 for문은 마지막 원소를 포함하지 않는다는 점을 기억하고 N-7까지로 정해준다.
- 체스판의 시작점에 따라서 색칠하는 경우가 달라진다.
- 또한 (i+j)가 짝수이면 시작점의 색과 동일하다는 특징이 있다.
- 따라서 시작점을 기준으로 체스판의 색을 체크하고, 바꿔야 하는 경우는 카운트해준다.
풀이
# (8*8) 크기의 체스판을 만들려고 함.
N, M = map(int, input().split()) # (M*N) 크기의 보드
# 8*8 크기의 모든 정사각형을 따로 빼서, 맨 위쪽 위칸을 기준으로 바꿔야 하는 색을 카운트 한다.
# 가장 적은 카운트 개수를 리턴한다.
board = [input() for _ in range(N)] # 주어진 입력판
count = []
for a in range(N-7):
for b in range(M-7):
index1 = 0 # W로 시작할 경우
index2 = 0 # B로 시작할 경우
for i in range(a, a+8):
for j in range(b, b+8):
if (i+j) % 2 == 0: # 시작점 체스판과 동일하다면,
if board[i][j] != 'W':
index1 += 1
if board[i][j] != 'B':
index2 += 1
else:
if board[i][j] != 'B':
index1 += 1
if board[i][j] != 'W':
index2 += 1
count.append(min(index1, index2))
print(min(count))
정리
- 완전 탐색 문제라는 종류파악은 쉬웠으나, 아이디어 구현에 조금 힘겨웠다.
- 특히 시작점 체스판의 색깔이 (i+j)가 짝수일 경우와 동일하다는 아이디어는 캐치하지 못했다.
- 완전 탐색이지만 구현에 있어서 조금 어려운 문제였다…
Uploaded by N2T
