[Kotlin] 백준 3967 - 매직 스타

1. 문제 요약

• 헥사그램 모양의 12칸에 1~12를 배치
• 여섯 개의 줄마다 서로 다른 4칸의 합이 모두 26이어야 한다.
• 입력은 5×9 보드:
  • A~L은 숫자 1~12를 의미
  • x는 빈칸
  • .는 모양 유지용
• 가능한 해 중 사전순으로 가장 앞서는 보드를 출력
• 항상 해가 존재하는 경우만 입력으로 주어진다.

---

2. 접근법

이 문제는 백트래킹(DFS) 으로 해결.

기본 아이디어

1. 12칸을 순서대로 채워나간다.
2. 이미 채워진 칸은 건너뛰고, 빈칸(x)은 아직 쓰지 않은 숫자 중 하나를 넣는다.
3. 여섯 개 줄의 합이 26인지 체크한다.

사전순 최소 해를 보장하는 방법

• 입력 보드를 행 → 열 순서로 스캔하여 12칸의 인덱스를 매긴다.
• DFS에서 숫자를 배치할 때는 1부터 12까지 오름차순으로 시도한다.
  → 최초로 완성되는 해가 곧 사전순 최소 해가 된다.

가지치기 최적화

탐색 공간을 줄이기 위해 각 줄을 부분적으로 검사한다.

• 부분합이 26을 초과하면 불가능.
• 네 칸이 모두 채워졌는데 26이 아니면 불가능.
• 네 칸이 덜 찼는데 이미 합이 26이면 이후 추가 숫자 때문에 반드시 초과 → 불가능.

---

3. 시간 및 공간 복잡도

• 시간복잡도: 최악의 경우 O(12!).
  하지만 부분합 가지치기를 통해 탐색 공간을 크게 줄일 수 있어 실제 수행은 매우 빠르다.
• 공간복잡도: O(12) (숫자 배열, 방문 체크, 좌표 기록 등)

---

4. 전체 코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    BufferedReader(InputStreamReader(System.`in`)).use { br ->
        val board = Array(5) { CharArray(9) }   // 입력 보드
        val pos = Array(12) { IntArray(2) }     // 헥사그램 12칸의 좌표 (행, 열)

        var idx = 0
        val numbers = IntArray(12)              // 각 칸에 놓인 값 (1~12), 미배치면 0
        val fixed = BooleanArray(12)            // 초기 입력에서 이미 고정된 칸 여부
        val used = BooleanArray(13)             // 숫자 사용 여부 (1~12)

        // 입력 처리
        for (i in 0 until 5) {
            val line = br.readLine()
            for (j in 0 until 9) {
                board[i][j] = line[j]
                if (board[i][j] == 'x' || board[i][j] in 'A'..'L') {
                    pos[idx][0] = i
                    pos[idx][1] = j
                    if (board[i][j] in 'A'..'L') {
                        val v = board[i][j] - 'A' + 1
                        numbers[idx] = v
                        fixed[idx] = true
                        used[v] = true
                    }
                    idx++
                }
            }
        }

        // 헥사그램 여섯 줄의 인덱스 집합
        val lines = arrayOf(
            intArrayOf(0, 2, 5, 7),
            intArrayOf(0, 3, 6, 10),
            intArrayOf(1, 2, 3, 4),
            intArrayOf(1, 5, 8, 11),
            intArrayOf(4, 6, 9, 11),
            intArrayOf(7, 8, 9, 10)
        )

        // 부분합 검사: 방금 배치한 인덱스 afterPlacedIdx가 포함된 줄만 확인
        fun partialValid(afterPlacedIdx: Int): Boolean {
            for (line in lines) {
                if (line.contains(afterPlacedIdx)) {
                    var sum = 0
                    var cnt = 0
                    for (p in line) {
                        if (numbers[p] != 0) {
                            sum += numbers[p]
                            cnt++
                        }
                    }
                    if (sum > 26) return false              // 합이 초과
                    if (cnt == 4 && sum != 26) return false // 다 채웠는데 합이 아님
                    if (cnt < 4 && sum == 26) return false  // 다 안 찼는데 합이 이미 26
                }
            }
            return true
        }

        // 최종적으로 모든 줄이 26인지 검사
        fun checkAll26(): Boolean {
            for (line in lines) {
                var s = 0
                for (p in line) s += numbers[p]
                if (s != 26) return false
            }
            return true
        }

        var done = false

        // DFS 탐색
        fun dfs(d: Int) {
            if (done) return
            if (d == 12) {
                if (checkAll26()) {
                    // 정답 해를 보드에 반영
                    for (i in 0 until 12) {
                        val (r, c) = pos[i]
                        board[r][c] = ('A'.code + numbers[i] - 1).toChar()
                    }
                    val sb = StringBuilder()
                    for (i in 0 until 5) {
                        sb.append(board[i].concatToString()).append('\n')
                    }
                    print(sb.toString())
                    done = true
                }
                return
            }

            if (fixed[d]) {
                // 고정된 칸은 바로 다음으로
                if (partialValid(d)) dfs(d + 1)
                return
            }

            // 빈칸: 1~12 오름차순으로 숫자 배치
            for (v in 1..12) {
                if (used[v]) continue
                numbers[d] = v
                if (partialValid(d)) {
                    used[v] = true
                    dfs(d + 1)
                    used[v] = false
                }
                numbers[d] = 0
                if (done) return
            }
        }

        dfs(0)
    }
}