백준 1018번: 체스판 다시 칠하기 - 상세 풀이
🔍 1. 문제 소개
8*8 크기의 체스판에서 검은색과 흰색 정사각형이 번갈아 배치되어야 합니다. M×N 크기의 보드가 주어지며, 각 칸은 검은색('B') 또는 흰색('W')으로 칠해져 있습니다. 보드에서 8×8 크기의 영역을 선택하여 체스판으로 만들려고 할 때, 다시 칠해야 하는 정사각형의 최소 개수를 구하는 문제입니다. 체스판의 왼쪽 위 칸이 흰색 또는 검은색인 두 가지 경우를 모두 고려해야 합니다.
💡 2. 문제 해석
핵심은 8×8 크기의 모든 가능한 영역을 탐색하여 각 영역에서 다시 칠해야 하는 정사각형의 개수를 계산하고, 그 중 최솟값을 찾는 것입니다. 제약 조건은 보드의 크기 (M, N)가 8 ≤ M, N ≤ 50 이라는 점입니다. 문제의 입력은 보드의 크기와 각 칸의 색깔 정보이며, 출력은 다시 칠해야 하는 정사각형의 최솟값입니다.
🧠 3. 접근 방법
브루트포스 방식을 사용합니다. M×N 보드에서 8×8 영역을 선택하는 모든 경우의 수를 순회하며, 각 영역에 대해 다시 칠해야 하는 정사각형의 개수를 계산합니다. 각 영역에 대해 왼쪽 위 칸이 흰색인 경우와 검은색인 경우 두 가지 경우를 모두 고려하여 최솟값을 선택합니다. 최솟값을 찾기 위해 minOf 함수를 사용합니다.
⚙️ 4. 구현 과정
- **입력 받기:** 보드의 크기 M, N과 보드의 각 행의 상태를 입력받습니다.
2. 8×8 영역 순회: 이중 반복문을 사용하여 8×8 영역을 선택하는 모든 경우의 수를 순회합니다. 외부 반복문은 행, 내부 반복문은 열을 나타냅니다. 3. 다시 칠해야 하는 정사각형 개수 계산: countRepaintOptimized 함수를 사용하여 각 8×8 영역에서 다시 칠해야 하는 정사각형의 개수를 계산합니다. 이 함수는 왼쪽 위 칸이 흰색인 경우와 검은색인 경우를 동시에 계산하여 최솟값을 반환합니다. 4. 최솟값 갱신: 각 8×8 영역에 대한 다시 칠해야 하는 정사각형의 개수를 계산하여 현재까지 찾은 최솟값과 비교하고, 더 작으면 최솟값을 갱신합니다. 5. 결과 출력: 최종적으로 찾은 최솟값을 출력합니다.
💻 5. 코드 설명
fun main() {
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
val board = mutableListOf()
for (i in 0 until n) {
board.add(readLine()!!)
}
var minRepaint = Int.MAX_VALUE
for (i in 0 until n - 7) {
for (j in 0 until m - 7) {
minRepaint = minOf(minRepaint, countRepaintOptimized(board, i, j))
}
}
println(minRepaint)
}
fun countRepaintOptimized(board: List, row: Int, col: Int): Int {
var repaintCountW = 0
var repaintCountB = 0
for (i in row until row + 8) {
for (j in col until col + 8) {
val expectedColorW = if ((i - row + j - col) % 2 == 0) 'W' else 'B'
val expectedColorB = if ((i - row + j - col) % 2 == 0) 'B' else 'W'
if (board[i][j] != expectedColorW) repaintCountW++
if (board[i][j] != expectedColorB) repaintCountB++
}
}
return minOf(repaintCountW, repaintCountB)
}
countRepaintOptimized 함수는 주어진 8x8 영역에서 왼쪽 위가 흰색일 때와 검은색일 때 각각 다시 칠해야 하는 칸의 수를 계산하고, 그 중 최솟값을 반환합니다. %2 == 0 연산을 통해 체스판 패턴을 효율적으로 계산합니다.
⏱️ 6. 시간 복잡도와 공간 복잡도 분석
* 시간 복잡도: O(N*M) 입니다. 8×8 영역을 선택하는 모든 경우의 수 ( (N-7)(M-7) )에 대해 O(64) 연산을 수행하므로, 전체 시간 복잡도는 O((N-7)(M-7)*64) ≈ O(NM) 입니다. N과 M이 최대 50이므로, 실제 수행 시간은 매우 빠릅니다.
* 공간 복잡도: O(NM) 입니다. 입력으로 받은 보드를 저장하는 공간이 필요합니다. 하지만 추가적인 공간 사용은 상수 크기이므로, 공간 복잡도는 입력 크기에 선형적으로 비례합니다.
🎯 7. 결론
이 문제는 브루트포스 방식으로 효율적으로 해결할 수 있습니다. 코드의 최적화를 통해 시간 복잡도는 O(NM)으로 유지되면서 불필요한 연산을 줄였습니다. 문제 해결 과정을 통해 이중 반복문을 사용한 브루트포스 방식과 최적화 기법을 이해할 수 있었습니다. 추가적인 개선으로는, 입력 크기가 매우 클 경우 더욱 효율적인 알고리즘을 고려할 수 있지만, 문제의 제약 조건 내에서는 현재 구현이 충분히 효율적입니다.