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

이 문제는 bfs, 트리를 이용해서 풀었다.

 

이 문제에서 노드의 수가 n일 때 간선의 수가 n - 1개이고, 모든 임의의 두 점은 연결되어있으므로 입력 그래프는 트리이다.

트리는 아무 점이나 루트로 잡아도 트리이므로, 1을 루트로 잡았다.

 

bfs를 이용해서 노드들의 depth를 계산한다.

 

bfs 이후에는 depth가 깊은 순서대로 내림차순 정렬 후 루프를 돌린다.

depth가 가장 깊은 리프 노드부터 자신의 부모를 확인한다. 이 때 자신이 이미 켜져있는 경우에는 continue한다.

만약 자신의 부모가 등대가 켜져있지 않다면 켜주고 answer++하는 방식으로 정답을 구할 수 있다.

 

문제에서 입력 그래프가 트리일 경우에는 bfs나 dfs를 이용한 풀이가 적용되는 경우가 많았던 것 같다.

#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;

#define MAX 100000

vector<int> edges[MAX + 1];
vector<int> nodes;
bool visited[MAX + 1];
vector<int> depth;
bool light[MAX + 1];

bool compare(int a, int b) {
    return depth[a] > depth[b];
}

void bfs(int root) {
    depth[root] = 0;
    visited[root] = true;
    queue<pair<int, int>> q;
    q.push({root, 0});
    
    while (!q.empty()) {
        int present = q.front().first;
        int presentDepth = q.front().second;
        q.pop();
        
        for (int next : edges[present]) {
            if (!visited[next]) {
                visited[next] = true;
                depth[next] = presentDepth + 1;
                q.push({next, presentDepth + 1});
            }
        }
    }
}

int findParent(int node) {
    for (int next : edges[node]) {
        if (depth[next] < depth[node]) {
            return next;
        }
    }
    return -1;
}

int solution(int n, vector<vector<int>> lighthouse) {
    int answer = 0;
    
    for (vector<int> edge : lighthouse) {
        int a = edge[0];
        int b = edge[1];
        
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    
    depth = vector<int>(n + 1, -1);
    bfs(1);
    
    for (int i = 1; i <= n; i++) {
        nodes.push_back(i);
        visited[i] = false;
    }
    
    sort(nodes.begin(), nodes.end(), compare);
    
    for (int node : nodes) {
        if (light[node]) {
            continue;
        }
        
        int parent = findParent(node);
        
        if (parent == -1) {
            bool flag = false;
            
            for (int next : edges[node]) {
                if (light[next]) {
                    flag = true;
                    break;
                }
            }
            if (!flag) {
                answer++;
            }
        }
        
        if (parent != -1 && !light[parent]) {
            light[parent] = true;
            answer++;
        }
    }
    
    return answer;
}