체스판 다시 칠하기 문제는 백준 플랫폼의 실버 4 난이도 문제로, 브루트 포스 알고리즘의 기본적인 이해와 구현 능력을 테스트합니다. 이 문제는 N×M 크기의 보드에서 8×8 크기의 완벽한 체스판을 만들기 위해 최소 몇 개의 칸을 다시 칠해야 하는지 찾는 것이 핵심입니다.
https://www.acmicpc.net/problem/1018
🧩 문제 이해하기
1. 문제 조건
- N×M 크기의 보드가 주어짐 (8 ≤ N, M ≤ 50)
- 각 칸은 검은색(B) 또는 흰색(W)으로 칠해져 있음
- 보드에서 8×8 크기의 체스판을 잘라내야 함
- 체스판은 검은색과 흰색이 번갈아 칠해져 있어야 함
- 다시 칠해야 하는 정사각형의 최소 개수를 구해야 함
2. 체스판의 특성
- 체스판은 검은색과 흰색이 번갈아 칠해져 있음
- 변을 공유하는 두 칸은 반드시 다른 색이어야 함
- 체스판을 색칠하는 경우는 두 가지뿐
– 맨 왼쪽 위 칸이 흰색(W)으로 시작하는 경우
– 맨 왼쪽 위 칸이 검은색(B)으로 시작하는 경우
🔍 알고리즘 접근법
1. 브루트 포스(완전 탐색) 방식
2. 시간 복잡도 분석
- 보드 크기가 최대 50×50인 경우, 가능한 8×8 체스판 위치는 (50-7)×(50-7) = 43×43 = 1,849개5
- 각 위치에서 64칸을 확인하므로 총 연산 수는 약 1,849×64×2 = 236,672번5
- 시간 제한 2초 내에 충분히 해결 가능8
💻 코드 구현
1. 문제 해결 전략
– 체스판 패턴 이해하기
– 8×8 영역 잘라내기
– 다시 칠해야 하는 칸 계산하기
2. 파이썬 코드
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
board = [input() for _ in range(N)]
ans = 64 # 최대 64칸을 모두 칠해야 하는 경우로 초기화
# 좌상단 y,x 좌표 기준, W일때와 B일때를 비교하여 최소값을 구하는 함수
def fill(y, x, bw):
global ans
cnt = 0
for i in range(8):
for j in range(8):
if (i + j) % 2 == 0: # 흰색이어야 하는 위치
if board[y+i][x+j] != bw:
cnt += 1
else: # 검은색이어야 하는 위치
if board[y+i][x+j] == bw:
cnt += 1
ans = min(ans, cnt)
# 가능한 모든 8×8 체스판 위치 탐색
for i in range(N-7):
for j in range(M-7):
# 흰색으로 시작하는 경우
fill(i, j, 'W')
# 검은색으로 시작하는 경우
fill(i, j, 'B')
print(ans)
3. 코드 설명
– 입력 처리
- N, M을 입력받고 N개 줄에 걸쳐 보드의 상태를 입력받음
ans를 64(8×8=64, 모든 칸을 다시 칠하는 최악의 경우)로 초기화
– 패턴 검사 함수 (fill)
- 좌상단 (y, x) 좌표와 시작 색(bw)을 매개변수로 받음
- 8×8 크기의 영역을 탐색하면서 다시 칠해야 하는 칸의 수 계산
- 행과 열의 합이 짝수/홀수인 위치에 따라 색 패턴 결정
- 계산된 값이 기존 최소값보다 작으면 갱신
– 모든 가능한 위치 탐색
- i는 0부터 N-8까지, j는 0부터 M-8까지 반복
- 각 위치에서 흰색(W)으로 시작하는 경우와 검은색(B)으로 시작하는 경우 모두 확인
🎲 예제 풀이 과정
1. 간단한 예제 분석
예를 들어, 8×8 크기의 보드에서:
textWBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW <- 여기에 오류가 있음 (BBB)
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
이 보드에서는 4번째 행의 세 번째와 네 번째 칸이 규칙에 맞지 않습니다. 하지만 흰색으로 시작하는 패턴을 따르면 하나만 다시 칠하면 되므로 답은 1입니다.2
2. 복잡한 예제 분석
좀 더 큰 보드(10×13)의 경우:
textBBBBBBBBWBWBW
BBBBBBBBBWBWB
...
이런 보드에서는 여러 가지 8×8 영역을 고려해야 합니다. 모든 위치에서 체스판 패턴을 검사한 결과, 최소 12개의 칸을 다시 칠해야 합니다.23
📊 알고리즘 최적화 방법
1. 누적합 활용
- 이 문제는 단순 브루트 포스 외에도 누적합을 활용하여 최적화할 수 있음5
- 누적합을 사용하면 각 8×8 영역을 계산할 때 중복 계산을 줄일 수 있음
- 하지만 기본 문제는 브루트 포스만으로도 시간 내에 해결 가능5
2. 패턴 인식 최적화
🏆 문제 풀이 요약
1. 핵심 아이디어
- 브루트 포스로 가능한 모든 8×8 체스판 위치 탐색
- 각 위치에서 두 가지 패턴(W 시작, B 시작) 검사
- 다시 칠해야 하는 최소 칸 수 계산
2. 중요 포인트
- 좌상단 기준점 설정 (i: 0 ~ N-8, j: 0 ~ M-8)
- 체스판 패턴 이해 (행+열의 합이 짝수/홀수에 따라 색 결정)
- 최소값 계속 갱신하며 탐색
이 문제는 브루트 포스 알고리즘의 기본 개념을 이해하고 체스판의 패턴을 파악하는 능력을 테스트합니다. 8×8 영역을 탐색하며 다시 칠해야 하는 칸의 수를 계산하는 과정에서 행과 열의 합의 홀짝성을 이용하여 효율적으로 패턴을 검사할 수 있습니다. 시간 복잡도는 O((N-7)×(M-7)×64)로, 주어진 제약 조건 내에서 충분히 해결 가능합니다.
Citations:
- https://www.acmicpc.net/problem/1018
- https://www.acmicpc.net/problem/1018
- https://pixx.tistory.com/561
- https://velog.io/@gayeong39/%EB%B0%B1%EC%A4%80-1018-%EC%B2%B4%EC%8A%A4%ED%8C%90-%EB%8B%A4%EC%8B%9C-%EC%B9%A0%ED%95%98%EA%B8%B0
- https://velog.io/@red-sprout/%EB%B0%B1%EC%A4%80-1018-%EC%B2%B4%EC%8A%A4%ED%8C%90-%EB%8B%A4%EC%8B%9C-%EC%B9%A0%ED%95%98%EA%B8%B0
- https://ittrue.tistory.com/60
- https://dev-mandos.tistory.com/141
- https://rightbellboy.tistory.com/211
- https://ceo-uk22.tistory.com/216
- https://st-lab.tistory.com/101
- https://dev-nicitis.tistory.com/62
- https://carrot-farmer.tistory.com/65
- https://greedy-blow-you-away12.tistory.com/40
- https://growth-coder.tistory.com/87
- https://windy7271.tistory.com/entry/Python%EB%B0%B1%EC%A4%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-1018%EB%B2%88-%EC%B2%B4%EC%8A%A4%ED%8C%90-%EB%8B%A4%EC%8B%9C-%EC%B9%A0%ED%95%98%EA%B8%B0
- https://kiffblog.tistory.com/203
- https://byungil.tistory.com/181
- https://10cheon00.tistory.com/9
- https://parkjunbackend.tistory.com/36
- https://bit-lab.tistory.com/21
- https://velog.io/@ggm0805/series/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8
