문제

풀이

리프 노드에서 시작해 올라가면서 생각하면 된다. 리프 노드는 하나의 노드와 연결되어 있고, 리프노드를 켜는 것보다는 부모 노드를 켜는것이 유리하므로 리프 노드의 부모 노드는 반드시 켜져야 한다.
같은 원리로 불이 켜진 노드의 부모 노드는 가능하면 꺼져 있어야 켜진 등대의 개수를 최소로 하는 것에 유리하다. 다만 1 - 2 - 3 - 4 처럼 있는 경우 2,3 번 노드는 서로 다른 리프 노드에서 시작해 올라오는 경우이므로 2,3번 노드는 모두 켜지게 된다.

이 원리를 코드에 적용하기 위해 위상정렬을 사용했다. 등대의 연결은 양방향 이므로 indegree가 0이 아닌 1인 경우가 리프노드가 된다는 점만 주의하면 된다.

코드

#include <string>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

int onoff[100001];
int indegree[100001];
int topology(vector<int> nodeArr[],int n){
    int answer=0;
    queue<int> q;

    for(int i=1;i<=n;i++){
        if(indegree[i]==1) {
            q.push(i);
        }
    }

    for(int i=1;i<=n;i++){
        if(q.empty()) return -1;
        int x = q.front();
        q.pop();
        
        for(int j=0;j<nodeArr[x].size();j++){
            int y = nodeArr[x][j];
            if(onoff[x]==0) onoff[y]=1;
            if(--indegree[y]==1){
                q.push(y);
            }
        }
    }
    for(int i=1;i<=n;i++) if(onoff[i]==1) answer++;
    return answer;
}

int solution(int n, vector<vector<int>> lighthouse) {
    vector<int> nodeArr[n+1];
    for(int i=0;i<lighthouse.size();i++){
        int node1 = lighthouse[i][0];
        int node2 = lighthouse[i][1];
        nodeArr[node1].push_back(node2);
        nodeArr[node2].push_back(node1);
        indegree[node1]++;
        indegree[node2]++;
    }
    
    return topology(nodeArr,n);
}