백준 1006번: 습격자 초라기 - 효율적인 해결 전략 🔍

1. 문제 소개 📝

백준 1006번 "습격자 초라기" 문제는 도넛 형태의 비밀국방기지 원타곤을 습격하는 초라기의 임무를 다룹니다. 원타곤은 N개의 구역으로 나뉘어 있으며, 각 구역에는 특정 수의 적이 배치되어 있습니다. 초라기는 W명의 특수소대를 이용하여 모든 구역을 침투해야 합니다. 한 특수소대는 인접한 최대 두 개의 구역을 동시에 침투할 수 있으며, 각 구역은 하나의 소대만 침투해야 합니다. 한 소대가 침투하는 구역의 적의 총 수는 W를 넘을 수 없습니다. 목표는 모든 구역을 침투하는 데 필요한 최소 특수소대 수를 구하는 것입니다.

2. 문제 해석 💡

문제는 그래프 이론의 최소 정점 피복 문제(Minimum Vertex Cover)와 유사합니다. 각 구역을 노드, 인접한 구역을 간선으로 생각하면, 최소한의 소대(노드)로 모든 구역(간선)을 커버해야 하는 문제가 됩니다. 단, 중요한 제약 조건은 각 소대의 수용 가능한 적의 수(W)가 존재한다는 점입니다. 따라서 단순히 최소 정점 피복 문제 알고리즘을 적용할 수 없고, 각 소대의 용량 제한을 고려해야 합니다.

3. 접근 방법 🧠

문제의 제약 조건(N의 크기)을 고려하여, 최적해를 보장하는 알고리즘(예: 정수 선형 계획법)보다 효율적인 근사 알고리즘을 사용하는 것이 좋습니다. 본 해결 전략에서는 탐욕적(Greedy) 접근 방식을 사용합니다. 각 구역을 순차적으로 처리하며, 아직 침투되지 않은 구역에 대해 새로운 소대를 배치합니다. 이때, 가능하다면 인접한 구역을 함께 침투하여 소대의 수를 최소화하려고 시도합니다.

4. 구현 과정 ⚙️

입력: N, W, 각 구역의 적의 수를 입력받습니다.
초기화: covered 리스트를 생성하여 각 구역이 침투되었는지 여부를 추적합니다. 소대 수를 저장할 teams 변수를 0으로 초기화합니다.
탐욕적 침투: 각 구역을 순차적으로 검사합니다. 만약 구역이 침투되지 않았다면:
- 새로운 소대를 배치하고 (teams 증가), 해당 구역을 침투되었음으로 표시합니다 (covered 업데이트).
- 인접한 구역 중 침투되지 않은 구역이 있고, 해당 구역과 현재 구역의 적의 수의 합이 W 이하라면, 인접 구역도 함께 침투합니다. (covered 업데이트).
출력: teams 변수(필요한 소대 수)를 출력합니다.

5. 코드 설명 💻


import sys

def solve():
    n, w = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))
    b = list(map(int, sys.stdin.readline().split()))
    
    teams = 0
    covered = [False] * n  # Only track the original nodes
    
    for i in range(n):
        if not covered[i]:
            teams += 1
            covered[i] = True
            
            # Try to cover neighbours if possible without exceeding weight limit
            if i > 0 and not covered[i-1] and a[i] + a[i-1] <= w:
                covered[i-1] = True
            if i < n - 1 and not covered[i+1] and a[i] + a[i+1] <= w:
                covered[i+1] = True
    
    print(teams)

t = int(sys.stdin.readline())
for _ in range(t):
    solve()

solve() 함수는 하나의 테스트 케이스를 처리합니다. covered 리스트는 각 구역(1~N)이 침투되었는지(True) 아니면 아닌지(False)를 나타냅니다. 도넛 구조의 두 번째 원은 첫 번째 원의 인접 정보를 통해 간접적으로 처리되므로 별도의 추적이 필요 없습니다. 탐욕적인 접근 방식은 for 루프 내에서 구현됩니다. 🔄

6. 성능 분석 ⏱️

시간 복잡도: O(N), 각 구역을 최대 한 번씩만 방문하기 때문입니다.
공간 복잡도: O(N), covered 리스트와 입력 배열 a, b 때문입니다.

7. 문제점과 해결방안 🛠️

위 접근 방식의 한계는 탐욕적 방법이 항상 최적해를 보장하지 않는다는 것입니다. 실제로 이 문제는 다이나믹 프로그래밍(DP)로 해결해야 정확한 최소값을 찾을 수 있습니다. DP 접근 방식은 각 구역의 다양한 조합 상태를 고려하고, 각 상태에서의 최적해를 계산합니다.


import java.util.*

fun main() {
    val scanner = Scanner(System.`in`)
    val t = scanner.nextInt()

    repeat(t) {
        val n = scanner.nextInt()
        val w = scanner.nextInt()

        val d = Array(2) { IntArray(n + 1) }
        for (j in 0..1) {
            for (i in 1..n) {
                d[j][i] = scanner.nextInt()
            }
        }

        val INF = Int.MAX_VALUE / 2
        val dp = Array(n + 1) { IntArray(3) { INF } }

        fun initDp() {
            for (i in 0..n) {
                for (j in 0..2) {
                    dp[i][j] = INF
                }
            }
        }

        val scenarios = mutableListOf(2)
        if (d[0][1] + d[0][n] <= w) scenarios.add(1)
        if (d[1][1] + d[1][n] <= w) scenarios.add(0)
        if (d[0][1] + d[0][n] <= w && d[1][1] + d[1][n] <= w) scenarios.add(-1)

        var ans = INF
        for (mode in scenarios) {
            initDp()
            dp[0][0] = 0
            dp[0][1] = 0
            dp[0][2] = 0

            for (i in 1..n) {
                if (!(i == 1 && (mode == 1 || mode == -1))) {
                    dp[i][0] = minOf(dp[i][0], dp[i - 1][2] + 1)
                    if (d[0][i - 1] + d[0][i] <= w) {
                        dp[i][0] = minOf(dp[i][0], dp[i - 1][1] + 1)
                    }
                } else {
                    dp[i][0] = 0
                }

                if (!(i == 1 && (mode == 0 || mode == -1))) {
                    dp[i][1] = minOf(dp[i][1], dp[i - 1][2] + 1)
                    if (d[1][i - 1] + d[1][i] <= w) {
                        dp[i][1] = minOf(dp[i][1], dp[i - 1][0] + 1)
                    }
                } else {
                    dp[i][1] = 0
                }

                if (!(i == 1 && mode == -1)) {
                    dp[i][2] = minOf(dp[i][0] + 1, dp[i][1] + 1, dp[i][2])
                    if (d[0][i] + d[1][i] <= w) {
                        dp[i][2] = minOf(dp[i][2], dp[i - 1][2] + 1)
                    }
                    if (i >= 2 && d[0][i - 1] + d[0][i] <= w && d[1][i - 1] + d[1][i] <= w) {
                        dp[i][2] = minOf(dp[i][2], dp[i - 2][2] + 2)
                    }
                } else {
                    dp[i][2] = 0
                }
            }

            when (mode) {
                2 -> ans = minOf(ans, dp[n][2])
                1, 0 -> ans = minOf(ans, dp[n][mode] + 1)
                -1 -> ans = minOf(ans, dp[n - 1][2] + 2)
            }
        }
        println(ans)
    }
}

이 코틀린 코드는 다이나믹 프로그래밍 접근 방식을 구현한 것으로, 모든 가능한 경우의 수를 고려하여 최적해를 찾습니다. 하지만 구현이 복잡하고 상태 전이를 정확히 처리해야 하는 어려움이 있습니다. 🧩

8. 결론 🎯

백준 1006번 "습격자 초라기" 문제는 그래프 이론과 다이나믹 프로그래밍의 개념을 결합하여 해결해야 하는 복잡한 문제입니다. 단순한 탐욕적 접근 방식으로는 최적해를 항상 찾을 수 없으며, 여러 초기 상태를 고려한 DP 접근법이 필요합니다.

이러한 유형의 문제는 상태 정의와 전이 함수를 명확히 설정하는 것이 중요하며, 다양한 초기 조건을 고려하여 최적해를 찾는 연습이 필요합니다. 실전에서는 이러한 복잡한 DP 문제를 해결하기 위해 문제를 작은 부분 문제로 분해하고, 각 부분 문제의 해결책을 결합하는 능력이 중요합니다. 💪

이 문제를 통해 그래프 이론, 다이나믹 프로그래밍, 그리고 최적화 문제에 대한 이해를 더욱 깊게 할 수 있습니다. 알고리즘 공부의 여정에서 이러한 복잡한 문제들을 해결해 나가며 성장해 보세요! 🚀

[백준 1006] 습격자 초라기