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

프로그래머스

 

난이도 : Level 3 
알고리즘 유형 : DFS 
풀이 시간 : 28분 

문제 풀이 

서로 다른 번호가 매겨진 등대 `n`개가 존재한다. 또한, 등대와 등대 사이를 오가는 뱃길이 `n - 1`개 존재하여 모든 등대는 서로 연결되어있다. 등대와 등대 사이를 오가는 뱃길을 밝히기 위해 양 등대 중 적어도 하나는 켜져있도록 등대를 켜 두어야 한다. 켜 두어야 하는 등대 개수의 최솟값을 return하자.

각 등대 간 적어도 하나씩 켜져있다.

문제에서 가장 중요시 되는 부분은 "두 정점 중 적어도 하나는 켜져있어야 된다"라는 점이다.

위 예제를 살펴보면, 불이 켜진 노드에는 여러 자식노드가 있음을 확인할 수 있고, 리프 노드의 모든 불은 다 꺼져 있는 것을 확인할 수 있다. 

리프 노드 : 3, 4, 7, 8, 10

또다른 예시 역시 마찬가지로 리프 노드인 `3, 4, 7, 8, 10`은 모두 불이 꺼져있는 것을 확인할 수 있다.

 

이를 통해 "리프 노드의 경우에는 불을 키지 않고, 한 노드에 최대한 많은 자식 노드가 붙어있는 경우에 대해서 불을 켜주자" 라는 로직으로 접근할 수 있을 것이다. 

 

그럼 리프노드인지 먼저 확인을 해야 할 것이다. 확인을 위해서 DFS 알고리즘을 사용할 수 있다.

 

먼저, 문제에서 모든 정점은 연결되어있다라고 명시를 하였기 때문에 우리는 각각의 노드에서 DFS 탐색을 진행하는 것이 아닌, 1번 노드에서 DFS를 시작하면 된다.

이후, 재귀적으로 DFS를 탐색하며 만약 리프 노드인 경우, 해당 노드에는 불꺼짐 상태(`turnon[u] = 0;`)를 저장한 뒤 return한다.

자식 노드에 대한 탐색이 끝난 뒤, 다시 부모 노드로 돌아와서, 만약 자식노드의 불이 꺼져있다면(`if (!turnon[graph[u][i]])`) 자신의 불을 키는 과정을 추가해주었다.

 

이를 통해 "두 노드 중 적어도 한 곳의 불이 켜져있어야 한다" 는 조건을 만족할 수 있다.

 

해당 노드의 자식 노드 중 어떤 노드라도 리프 노드라면, 해당 노드의 불을 켜주어야 한다. 이후, 상향식으로 올라가며 자식 노드의 불이 켜진 경우에는 굳이 불을 켜지 않도록 설정하고, 자식 노드의 불이 안켜진 경우에만 켜주는 식으로 하면 불을 켜는 최소 개수를 구할 수 있다.

 

해당 로직의 시간복잡도는 정점의 개수 $≤ 100000$, 엣지의 개수 $≤ 100000 - 1$에 대해 DFS 를 진행하였기 때문에, 최악의 경우, $O(n + n - 1)$이 된다.

 

코드

/*
두 노드 중 적어도 하나는 켜져있어야 함
- 현재 도착한 노드에 리프노드가 없으면, 이전 노드를 무조건 켜준다.
- dfs 돌면서 return값이 0이면 현재 light를 킨다. 
- 1번 노드에서만 출발해도 된다.
*/

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int visited[100001] = {0, };
int turnon[100001] = {0, };

void dfs(int u, vector<vector<int>> &graph){
    visited[u] = 1;
    if (graph[u].empty()){
        turnon[u] = 0;
        // cout << u << '\n';
        return;
    }
        
    for (int i=0;i<graph[u].size();i++){
        if (!visited[graph[u][i]]){
            dfs(graph[u][i], graph);
            if (!turnon[graph[u][i]])
                turnon[u] = 1;
        }
    }
}

int solution(int n, vector<vector<int>> lighthouse) {
    vector<vector<int>> graph(n + 1);
    for (int i=0;i<n - 1;i++){
        graph[lighthouse[i][0]].push_back(lighthouse[i][1]);
        graph[lighthouse[i][1]].push_back(lighthouse[i][0]);
    }
    
    dfs(1, graph);
    
    int answer = 0;
    for (int i=0;i<n + 1;i++){
        if (turnon[i])
            answer++;
    }
    return answer;
}

배운 점 

seg fault가 몇 번 발생하였던 경우를 제외하면 쉽게 풀어나갈 수 있었던 문제이다. 

이번에 문제를 풀며 본인에게 칭찬하고 싶은 점은 그래프 문제를 마주했을 때 무조건 bfs 적으로 생각하는 사고를 떨쳐냈던 부분이다. 
문제를 자세히 읽고, 그래프 문제를 풀기 위한 적합한 알고리즘을 선택하는 과정이 문제풀이시간의 효율을 매우 높일 수 있다는 사실을 다시 한 번 깨닫는 문제풀이였다.