백준 1014번: 컨닝 - 상세 풀이
🔍 1. 문제 소개
백준 1014번 "컨닝" 문제는 N행 M열 크기의 교실에서 학생들이 시험을 보는 상황을 모델링합니다. 각 학생은 자신의 왼쪽, 오른쪽, 왼쪽 대각선 위, 오른쪽 대각선 위에 앉은 학생의 답지를 볼 수 있습니다. 일부 자리는 학생이 앉을 수 없도록 책상이 부서져 있습니다. 문제는 컨닝이 불가능하도록 학생들을 배치했을 때, 교실에 배치할 수 있는 최대 학생 수를 구하는 것입니다.
💡 2. 문제 해석
문제의 핵심은 서로 컨닝이 가능한 자리에 두 명 이상의 학생이 앉지 않도록 배치하는 것입니다. 즉, 어떤 학생도 자신의 왼쪽, 오른쪽, 왼쪽 대각선 위, 오른쪽 대각선 위에 다른 학생이 앉아있으면 안 됩니다. 또한, 일부 자리는 'x'로 표시되어 학생이 앉을 수 없습니다. 문제의 입력은 교실의 크기(N, M)와 각 자리의 상태('.' 또는 'x')이며, 출력은 최대 학생 수입니다.
🧠 3. 접근 방법
이 문제는 비트마스크와 동적 계획법(Dynamic Programming)을 사용하여 효율적으로 해결할 수 있습니다.
* 비트마스크: 각 행의 학생 배치 상태를 비트마스크로 표현합니다. M개의 열이 있으므로, 0부터 2M - 1까지의 정수가 각 행의 모든 가능한 배치 상태를 나타낼 수 있습니다. 각 비트는 해당 열에 학생이 앉았는지 (1) 아니면 비어있는지 (0)를 나타냅니다.
* 동적 계획법: dp[row][mask] 배열을 정의하여, row 번째 행까지 고려했을 때, row 번째 행의 배치 상태가 mask 일 때의 최대 학생 수를 저장합니다. 우리는 각 행에 대해 가능한 모든 배치 상태를 검사하고, 컨닝이 발생하지 않는 경우에만 다음 행으로 진행하며 최대 학생 수를 갱신합니다.
⚙️ 4. 구현 과정
- **입력 받기:** 교실의 크기 N, M과 각 자리의 상태를 입력받습니다.
- **
isSafe(row, mask, prevMask)함수:** 주어진 행row의 비트마스크mask와 이전 행prevMask에 대해, 컨닝이 발생하지 않는지 확인하는 함수를 구현합니다. 비트 연산을 사용하여 효율적으로 확인합니다. - **
countSetBits(mask)함수:** 주어진 비트마스크mask에서 설정된 비트(학생)의 수를 세는 함수를 구현합니다. - **DP 초기화:** 첫 번째 행에 대해 가능한 모든 마스크를 검사하고, 안전한 경우
dp[0][mask]에 학생 수를 저장합니다. - **DP 전이:** 두 번째 행부터 마지막 행까지 각 행의 가능한 모든 마스크에 대해, 이전 행의 모든 가능한 마스크를 검사하며 안전 조건을 만족하는 경우 DP 테이블을 업데이트합니다.
- **최대 학생 수 찾기:** DP 테이블 전체에서 최대 값을 찾아 출력합니다.
💻 5. 코드 설명
fun solve() {
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
val classroom = Array(n) { readLine()!!.toCharArray() }
val dp = Array(n) { IntArray(1 shl m) { 0 } }
fun isSafe(row: Int, mask: Int, prevMask: Int): Boolean {
for (i in 0 until m) {
if (mask and (1 shl i) != 0) {
if (classroom[row][i] == 'x') return false
if (i > 0 && (mask and (1 shl (i - 1)) != 0)) return false // 왼쪽
if (i < m - 1 && (mask and (1 shl (i + 1)) != 0)) return false // 오른쪽
if (row > 0) {
if (i > 0 && (prevMask and (1 shl (i - 1)) != 0)) return false // 왼쪽 대각선 위
if (i < m - 1 && (prevMask and (1 shl (i + 1)) != 0)) return false // 오른쪽 대각선 위
}
}
}
return true
}
fun countSetBits(mask: Int): Int {
var count = 0
for (i in 0 until m) {
if (mask and (1 shl i) != 0) {
count++
}
}
return count
}
for (mask in 0 until (1 shl m)) {
if (isSafe(0, mask, 0)) {
dp[0][mask] = countSetBits(mask)
}
}
for (row in 1 until n) {
for (currentMask in 0 until (1 shl m)) {
if (isSafe(row, currentMask, 0)) {
val currentStudentCount = countSetBits(currentMask)
for (prevMask in 0 until (1 shl m)) {
if (isSafe(row, currentMask, prevMask)) {
dp[row][currentMask] = maxOf(dp[row][currentMask], (dp.getOrNull(row - 1)?.get(prevMask) ?: 0) + currentStudentCount)
}
}
}
}
}
var maxStudents = 0
for (i in 0 until n) {
for (j in 0 until (1 shl m)) {
maxStudents = maxOf(maxStudents, dp[i][j])
}
}
println(maxStudents)
}
fun main() {
val c = readLine()!!.toInt()
repeat(c) {
solve()
}
}
isSafe 함수는 비트 연산을 사용하여 효율적으로 컨닝 여부를 검사합니다. dp 배열은 각 행의 가능한 배치 상태에 따른 최대 학생 수를 저장합니다.
⏱️ 6. 시간 복잡도와 공간 복잡도 분석
* 시간 복잡도: O(N * 22M). 각 행에 대해 2M개의 가능한 상태를 검사하고, 각 상태에 대해 이전 행의 2M개의 상태를 비교합니다.
* 공간 복잡도: O(N * 2M). dp DP 테이블의 크기가 N * 2M입니다.
🎯 7. 결론
이 문제는 비트마스크와 동적 계획법을 활용하여 효율적으로 해결할 수 있습니다. 비트 연산을 통해 상태를 효율적으로 표현하고, 동적 계획법을 통해 모든 가능한 안전한 배치 조합을 탐색하여 최대 학생 수를 찾습니다.