코딩 테스트 - 등대

등대

문제 링크 : 등대

문제 설명

인천 앞바다에는 1부터 n까지 서로 다른 번호가 매겨진 등대 n개가 존재합니다. 등대와 등대 사이를 오가는 뱃길이 n-1개 존재하여, 어느 등대에서 출발해도 다른 모든 등대까지 이동할 수 있습니다. 등대 관리자 윤성이는 전력을 아끼기 위하여, 이 중 몇 개의 등대만 켜 두려고 합니다. 하지만 등대를 아무렇게나 꺼버리면, 뱃길을 오가는 배들이 위험할 수 있습니다. 한 뱃길의 양쪽 끝 등대 중 적어도 하나는 켜져 있도록 등대를 켜 두어야 합니다.

예를 들어, 아래 그림과 같이 등대 8개와 7개의 뱃길들이 있다고 합시다. 이 경우 1번 등대와 5번 등대 두 개만 켜 두어도 모든 뱃길은 양쪽 끝 등대 중 하나가 켜져 있으므로, 배들은 안전하게 운항할 수 있습니다.

등대의 개수 n과 각 뱃길이 연결된 등대의 번호를 담은 이차원 배열 lighthouse가 매개변수로 주어집니다. 윤성이가 켜 두어야 하는 등대 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한 사항

• 2 ≤ n ≤ 100,000
• lighthouse의 길이 = n – 1
  • lighthouse 배열의 각 행 [a, b]는 a번 등대와 b번 등대가 뱃길로 연결되어 있다는 의미입니다.
    • 1 ≤ a ≠ b ≤ n
    • 모든 등대는 서로 다른 등대로 이동할 수 있는 뱃길이 존재하도록 입력이 주어집니다.

입출력 예

n	lighthouse	result
8	[[1, 2], [1, 3], [1, 4], [1, 5], [5, 6], [5, 7], [5, 8]]	2
10	[[4, 1], [5, 1], [5, 6], [7, 6], [1, 2], [1, 3], [6, 8], [2, 9], [9, 10]]	3

풀이 방법

• 먼저 입력되는 구조가 트리 형식이다. 그리고 각 edge마다 양쪽 중에 최소 하나는 등대가 있어야 하면서 최소 등대 수를 구하는 문제이다.
• 트리 형식이기 때문에 루트 노드를 지정해서 루트 노드로부터 내려가면서 하나씩 등대가 있는 경우하고 등대가 없는 경우를 구분하고 dp를 통해서 올라오면서 루트 노드에 정답을 저장하고자 했다.
• 간단하게 구현하기 위해 노드별로 등대 있는 경우, 없는 경우를 2차원 배열로 선언해서 필요한 등대의 최소 개수를 저장했다. dfs로 인접 리스트를 통해 순회하면서 해당 노드의 등대가 없는 경우에는 인접한 거는 무조건 등대가 있어야 하기 때문에 해당 경우의 등대만 더했고, 등대가 있는 경우에는 인접한 거 중에서 작은 케이스를 더했다.
  -> 해당 문제 풀이는 dfs를 통해 문제를 해결해서 O(V+E)의 시간복잡도를 가지고, V와 E는 각각 최대 100,000, 99,999이기 때문에 알맞은 알고리즘으로 보인다.

구현

#include <string>
#include <vector>

using namespace std;

void dfs(int u, vector<vector<int>>& dp, vector<bool>& visited, vector<vector<int>>& graph) {
    visited[u] = true;
    dp[u][0] = 0;
    dp[u][1] = 1;
    
    for(int v : graph[u]){
        if (!visited[v]){
            dfs(v, dp, visited, graph);
            
            // 등대 없으면, 인접한 거는 무조건 있어야 함
            dp[u][0] += dp[v][1];
            
            // 등대 있으면, 인접한 거는 뭐든 상관없음
            dp[u][1] += min(dp[v][0], dp[v][1]);
        }
    }
}

int solution(int n, vector<vector<int>> lighthouse) {
    vector<vector<int>> graph(n + 1);
    for(vector<int> v : lighthouse){
        graph[v[0]].push_back(v[1]);
        graph[v[1]].push_back(v[0]);
    }
    
    // 0 -> 등대 없음 / 1 -> 등대 있음
    vector<vector<int>> dp(n + 1, vector<int>(2, 0));
    vector<bool> visited(n + 1, false);
    
    dfs(1, dp, visited, graph);
    
    return min(dp[1][0], dp[1][1]);
}