[프로그래머스][C++] 등대

등대

문제 링크

등대

분석

켜져야하는 등대 개수의 최소값을 반환해야합니다.

n개의 등대와 n - 1개의 뱃길로 구성된 트리가 주어집니다.
여기서 등대는 노드를 뱃길은 간선을 의미합니다.

각 간선의 양쪽 끝 중 최소한 하나의 등대는 켜져있어야 합니다.

트리 + DP 형식의 문제입니다.

풀이

#include <vector>
#include <algorithm>

using namespace std;

// 그래프 구조를 인접 리스트로 표현
vector<vector<int>> graph;

// dp[node][0] -> node를 끄는 경우로 해당 서브트리에서 필요한 최소 등대 수입니다.
// dp[node][1] -> node를 켜는 경우로 해당 서브트리에서 필요한 최소 등대 수입니다.
vector<vector<int>> dp;

// 방문 여부를 저장합니다.
vector<bool> visited;

// 후위 순회 DFS로 트리 DP를 계산하는 함수
void dfs(int node)
{
    visited[node] = true;
    dp[node][0] = 0;    // node를 켜는 경우 -> 자식키 모두 켜져 있어야한다.
    dp[node][1] = 1;    // node를 끄는 경우 -> 자기 자신이 켜져있으니 1개 포함한다.
    
    // 연결된 자식 노드 순회
    for (int neighbor : graph[node])
    {
        // 방문 하지 않았던 노드인 경우
        if (!visited[neighbor])
        {
            // 자식 먼저 방문한다. (후위 순회)
            dfs(neighbor);
            
            // node가 꺼져 있는 경우, 자식은 반드시 켜져있어야 한다.
            dp[node][0] += dp[neighbor][1];

            // node가 켜져 있는 경우, 자식은 켜져도 되고 꺼져도 되므로 최소 값을 선택한다.
            dp[node][1] += min(dp[neighbor][0], dp[neighbor][1]);
        }
    }
}

int solution(int n, vector<vector<int>> lighthouse) {
    int answer = 0;
    
    // 1-based index를 사용합니다.
    graph.assign(n + 1, vector<int>());
    dp.assign(n + 1, vector<int>(2, 0));
    visited.assign(n + 1, false);
    
    // 등대 간의 연결 정보를 무방향 그래프로 구성
    for (const auto& edge : lighthouse)
    {
        int u = edge[0];
        int v = edge[1];
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    // 임의의 루트 노드부터 DFS 수행 (1이 아닌 다른 어느 노드든 가능)
    dfs(1);
    
    // 루트 노드를 켰을 때, 끄고 자식이 켜졌을 때 중 최소 값이 정답이다.
    answer = min(dp[1][0], dp[1][1]);
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n)$입니다.

• 그래프 구성 $O(n)$
• DFS 함수의 호출 $O(n)$
• DP 연산 횟수 $O(n)$

공간 복잡도는 $O(n)$입니다.

• 인접 리스트를 저장한 벡터 graph $O(2 \times (n - 1))$
• 필요한 최소 등대 수를 저장한 벡터 DP $O((n + 1) \times 2)$
• 방문 여부를 저장하는 벡터 visited $O(n + 1)$
• $O(n) + O(n) + O(n)$

테스트 성능

테스트 1 〉 통과 (31.96ms, 32.7MB)
테스트 2 〉 통과 (28.99ms, 32.6MB)
테스트 3 〉 통과 (31.02ms, 32.6MB)
테스트 4 〉 통과 (26.14ms, 32.8MB)
테스트 5 〉 통과 (29.79ms, 32.5MB)
테스트 6 〉 통과 (25.16ms, 32.9MB)
테스트 7 〉 통과 (22.11ms, 32.9MB)
테스트 8 〉 통과 (31.76ms, 32.3MB)
테스트 9 〉 통과 (29.50ms, 32.9MB)
테스트 10 〉 통과 (29.30ms, 32.4MB)
테스트 11 〉 통과 (13.56ms, 18MB)
테스트 12 〉 통과 (8.07ms, 11.9MB)
테스트 13 〉 통과 (2.40ms, 6.07MB)
테스트 14 〉 통과 (0.01ms, 4.12MB)
테스트 15 〉 통과 (0.22ms, 4.2MB)
테스트 16 〉 통과 (1.16ms, 4.64MB)