[알고리즘 문제] 동적 계획법 - 프로그래머스 등대(level 3)

문제 이해

등대 n개와 뱃길 n - 1개가 있고 모든 등대가 서로 연결되어 있습니다. 각 뱃길의 양 끝 등대 가운데 적어도 하나를 켜면서, 켜는 등대 수를 최소화해야 합니다.

뱃길 (a, b)가 안전하려면
a가 켜져 있거나 b가 켜져 있어야 한다.

그래프 관점에서는 모든 간선이 선택된 정점 하나 이상과 맞닿도록 최소 개수의 정점을 고르는 최소 버텍스 커버 문제입니다. 일반 그래프에서는 어렵지만 입력이 트리이므로 자식 서브트리의 답을 합치는 DP를 사용할 수 있습니다.

트리 문제로 바라보기

뱃길이 n - 1개이고 모든 등대가 연결되어 있으므로 입력 그래프는 트리입니다. 간선은 방향이 없으므로 인접 리스트에 양방향으로 저장하고, 임의의 등대인 1번을 루트로 정합니다.

vector<vector<int>> graph(n + 1);

for (const auto& edge : lighthouse) {
    int a = edge[0];
    int b = edge[1];
    graph[a].push_back(b);
    graph[b].push_back(a);
}

루트는 계산 순서를 정하기 위한 기준일 뿐 답에는 영향을 주지 않습니다. 모든 간선의 조건은 부모와 자식 사이에서도 그대로 유지되기 때문입니다.

DP 상태 정의

각 노드에서 필요한 정보는 현재 등대를 끄는 경우와 켜는 경우의 최소 개수입니다.

dp[node][0]: node를 끈 상태에서 node의 서브트리를 안전하게 만드는 최소 개수
dp[node][1]: node를 켠 상태에서 node의 서브트리를 안전하게 만드는 최소 개수

리프 노드는 자식이 없습니다. 리프를 끄면 켠 등대가 없으므로 0, 켜면 자기 자신 하나를 세므로 1입니다. 이 정의는 모든 노드의 초기값으로도 사용할 수 있습니다.

dp[node][0] = 0;
dp[node][1] = 1;

점화식 만들기

부모와 자식을 잇는 뱃길 하나를 기준으로 두 경우를 나누면 점화식이 자연스럽게 나옵니다.

1. 현재 등대를 끈 경우: 부모 쪽 끝이 꺼져 있으므로 뱃길을 안전하게 만들려면 자식은 반드시 켜야 합니다.
2. 현재 등대를 켠 경우: 이미 현재 등대가 뱃길을 덮고 있으므로 자식은 켜도 되고 꺼도 됩니다. 둘 중 더 작은 값을 선택합니다.

dp[node][0] += dp[child][1];
dp[node][1] += min(dp[child][0], dp[child][1]);

핵심은 꺼진 노드끼리는 부모와 자식 관계가 될 수 없다는 점입니다. 둘 다 꺼지면 그 사이의 뱃길 양 끝이 모두 꺼져 조건을 위반합니다.

예제로 계산하기

첫 번째 예시를 1번 등대를 루트로 놓으면 다음과 같습니다.

          1
      / / | \
     2 3  4  5
             /|\
            6 7 8

리프 2, 3, 4, 6, 7, 8은 모두 [0, 1]로 시작합니다. 5번을 끄면 세 자식이 모두 켜져야 하므로 dp[5][0] = 3입니다. 5번을 켜면 각 자식의 더 작은 상태인 꺼짐을 선택할 수 있으므로 dp[5][1] = 1입니다.

dp[5][0] = dp[6][1] + dp[7][1] + dp[8][1]
         = 1 + 1 + 1 = 3

dp[5][1] = 1
         + min(dp[6][0], dp[6][1])
         + min(dp[7][0], dp[7][1])
         + min(dp[8][0], dp[8][1])
         = 1

같은 방식으로 루트까지 계산하면 dp[1][0] = 2, dp[1][1] = 2가 됩니다. 루트에는 부모가 없으므로 켜짐과 꺼짐 중 작은 값인 2가 정답입니다.

후위 순회가 필요한 이유

부모의 값을 계산하려면 모든 자식의 DP 값이 먼저 완성되어야 합니다. 재귀 DFS라면 자식을 호출한 뒤 점화식을 적용해야 합니다. 또한 무방향 인접 리스트에는 부모도 이웃으로 들어 있으므로 부모를 다시 방문하지 않도록 제외해야 합니다.

void dfs(int node, int parent) {
    for (int child : graph[node]) {
        if (child == parent) continue;

        dfs(child, node);  // 자식을 먼저 계산
        dp[node][0] += dp[child][1];
        dp[node][1] += min(dp[child][0], dp[child][1]);
    }
}

다만 이 문제는 n이 최대 100,000입니다. 트리가 한 줄처럼 이어지면 재귀 깊이도 100,000이 되어 실행 환경에 따라 스택 오버플로가 발생할 수 있습니다. 최종 구현에서는 스택으로 부모와 방문 순서를 기록한 뒤, 방문 순서를 거꾸로 순회해 재귀 없는 후위 순회를 만듭니다.

최종 코드

#include <algorithm>
#include <array>
#include <vector>

using namespace std;

int solution(int n, vector<vector<int>> lighthouse)
{
    vector<vector<int>> graph(n + 1);

    for (const auto& edge : lighthouse) {
        int a = edge[0];
        int b = edge[1];
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    vector<int> parent(n + 1, 0);
    vector<int> order;
    order.reserve(n);

    vector<int> stack = {1};
    parent[1] = -1;

    while (!stack.empty()) {
        int node = stack.back();
        stack.pop_back();
        order.push_back(node);

        for (int next : graph[node]) {
            if (next == parent[node]) {
                continue;
            }

            parent[next] = node;
            stack.push_back(next);
        }
    }

    vector<array<int, 2>> dp(n + 1, {0, 1});

    for (auto it = order.rbegin(); it != order.rend(); ++it) {
        int node = *it;

        for (int next : graph[node]) {
            if (parent[next] != node) {
                continue;
            }

            dp[node][0] += dp[next][1];
            dp[node][1] += min(dp[next][0], dp[next][1]);
        }
    }

    return min(dp[1][0], dp[1][1]);
}

첫 번째 순회는 루트에서 각 노드의 부모와 방문 순서를 정합니다. 두 번째 순회는 그 순서를 뒤집어 자식부터 부모 방향으로 DP를 합칩니다. parent[next] == node인 이웃만 자식으로 처리하므로 부모 방향의 간선을 중복 계산하지 않습니다.

복잡도와 주의점

• 시간복잡도는 O(n)
• 인접 리스트를 만들고 두 번 순회하는 동안 각 노드와 간선을 상수 번 확인합니다.
• 공간복잡도는 O(n)
• 인접 리스트, 부모 배열, 방문 순서, DP 배열이 모두 등대 수에 비례합니다.
• 점화식은 자식 계산 뒤에 적용한다
• 부모의 상태는 완성된 자식 상태에 의존하므로 전위 순서로 합치면 아직 계산되지 않은 초기값을 사용하게 됩니다.
• 루트의 두 상태를 모두 비교한다
• 루트에는 부모 간선이 없어 켜짐을 강제하는 조건이 없습니다. 따라서 최종 답은 min(dp[root][0], dp[root][1])입니다.
• 입력 크기에 맞는 순회 방식을 고른다
• 재귀형 점화식은 이해하기 쉽지만 최악의 트리 깊이를 고려하면 반복형 구현이 더 안전합니다.

정리

• 연결된 n개 정점과 n - 1개 간선이므로 입력은 트리다.
• 모든 뱃길을 덮는 최소 등대 집합은 트리의 최소 버텍스 커버다.
• dp[node][0]은 현재 등대를 끈 경우, dp[node][1]은 켠 경우의 최소 개수다.
• 현재 등대를 끄면 모든 자식을 켜야 하고, 켜면 자식의 두 상태 중 작은 값을 선택한다.
• 자식부터 부모로 계산하고, 루트의 두 상태 중 작은 값을 반환한다.

처음에는 정수 삼각형처럼 아래에서 위로 값을 쌓는 문제라고 생각했습니다. 방향은 맞았지만 트리에서는 각 노드가 선택됐는지에 따라 자식에게 허용되는 상태가 달라진다는 점이 추가됩니다. 하나의 최솟값만 저장하지 않고 선택 여부를 상태로 분리하자, 뱃길의 안전 조건이 그대로 점화식으로 이어졌습니다.