한번사는인생

1

문제 분석과 접근 방법

문제를 처음 읽었을 때, 8x8 크기의 체스판을 만들기 위해 여러 위치에서 시작하여 체스판을 다시 칠해야 한다는 점에서 복잡해 보였습니다. 문제의 핵심은 큰 체스판에서 8x8의 부분 체스판을 잘라내고, 그 부분이 흑백 패턴을 유지하도록 칠해야 한다는 것이었습니다. 이를 위해 여러 가지 경우를 고려해 보아야 했습니다.

접근 방법을 정리해 보았습니다:

1. 전체 체스판에서 8x8의 부분 체스판을 모두 탐색합니다
2. 체스판의 크기는 N x M이기 때문에 (N-7) x (M-7)의 위치에서 8x8 체스판을 시작할 수 있습니다. 각 위치에서 8x8의 부분 체스판을 슬라이딩 윈도우처럼 잘라내어 검토합니다
3. 각 8x8 체스판에 대해 두 가지 경우의 수를 확인합니다
4. 체스판의 첫 번째 칸이 흰색인 경우와 검은색인 경우를 각각 고려해야 합니다. 따라서 두 개의 체스판 패턴 (WBWB... 혹은 BWBW...)을 모두 비교하여 최소로 칠해야 할 칸의 개수를 계산합니다
5. 모든 경우의 수에서 최소값을 찾습니다
6. 각 8x8 체스판마다 두 가지 패턴을 비교한 뒤, 그 중에서 최소로 칠해야 하는 칸의 수를 기록하고, 전체 탐색이 끝난 후 가장 작은 값을 찾습니다

이 문제를 풀기 위해서는 전체 체스판을 순회하며 작은 체스판을 하나하나 검사하는, 일종의 브루트 포스 방식이 필요했습니다. 브루트 포스가 효율적인 이유는 문제에서 제공하는 N과 M의 크기가 비교적 작아 모든 경우의 수를 시도해도 시간 내에 해결이 가능하기 때문입니다.

2

구현 시 생각해본 점들

문제를 구현하면서 몇 가지 고려해야 할 점들이 있었습니다

1. 체스판의 규칙성 유지 체스판은 규칙적으로 흑과 백이 교차하는 형태를 가져야 하기 때문에, 이 규칙을 그대로 적용하여 비교를 간단히 만들 수 있었습니다. 이를 위해 두 가지 가능한 체스판의 초기 상태를 문자열 배열로 미리 준비해 두었고, 각 부분 체스판을 탐색할 때마다 미리 준비된 패턴과 비교하는 방식으로 접근했습니다
2. 브루트 포스의 타당성 처음에는 브루트 포스 방식으로 모든 8x8 부분 체스판을 검사하는 것이 비효율적일까 걱정했지만, 문제의 제한 조건이 크지 않기 때문에 모든 경우를 탐색해도 충분히 시간 내에 풀 수 있다는 점을 깨달았습니다. 때로는 효율성보다 명료한 풀이가 더 중요한 경우가 있음을 다시 느꼈습니다
3. 최소 변경 횟수 계산 각 부분 체스판에서 변경해야 하는 칸의 수를 계산할 때, 첫 번째 칸의 색상에 따라 두 가지 경우를 나눠 각각 계산했습니다. 이를 통해 두 가지 패턴을 모두 고려하여 더 적은 변경 횟수를 선택할 수 있었습니다. 이 과정에서 코드의 가독성을 위해 함수를 나눠서 작성한 것이 도움이 되었습니다

3

코드 구현

N, M = map(int, input().split())
board = [input() for _ in range(N)]

# 체스판 패턴 미리 정의
pattern1 = ["WBWBWBWB", "BWBWBWBW"] * 4
pattern2 = ["BWBWBWBW", "WBWBWBWB"] * 4

def count_paint(x, y, pattern):
    count = 0
    for i in range(8):
        for j in range(8):
            if board[x + i][y + j] != pattern[i][j]:
                count += 1
    return count

min_paint = float('inf')

# 8x8 체스판 탐색
for i in range(N - 7):
    for j in range(M - 7):
        paint1 = count_paint(i, j, pattern1)
        paint2 = count_paint(i, j, pattern2)
        min_paint = min(min_paint, paint1, paint2)

print(min_paint)

4

문제 해결 후 느낀 점

이 문제를 해결하면서 작은 부분 문제로 나누어 전체 문제를 해결하는 방법의 중요성을 다시금 느꼈습니다. 8x8 크기의 체스판을 반복해서 검사해야 하기 때문에 반복문을 어떻게 구조화할지, 그리고 각 부분 체스판에서 색상 변경을 어떻게 계산할지에 대한 논리적인 접근이 필요했습니다. 또한, 복잡한 문제도 단계별로 접근해 나가면 충분히 풀 수 있다는 자신감을 가지게 되었습니다.

이 문제는 특히 브루트 포스의 중요성을 다시 한 번 되새길 수 있는 좋은 기회였어요. 때로는 가장 단순한 방식이 가장 효과적인 해결책이 될 수 있음을 기억하게 되었습니다. 또한, 체스판처럼 시각적이고 규칙적인 패턴을 가진 문제를 다룰 때에는 시각적으로 그려보거나, 패턴을 코드로 표현하는 연습이 큰 도움이 되겠다는 생각도 들었습니다.

문제를 해결하면서 생긴 작은 시행착오들이 앞으로의 문제 해결에 좋은 밑거름이 되기를 기대합니다. 앞으로도 이러한 경험을 바탕으로 더 많은 문제들을 해결해 나가고 싶습니다.