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

https://school.programmers.co.kr/learn/courses/30/lessons/133500#

프로그래머스

 

 

트리이므로 싸이클이 없으며 모든 노드는 연결되어 있고 노드가 n개 있을 때 엣지의 수는 n-1이다.

따라서 하나의 노드를 루트 노드로 잡고 리프 노드까지 내려간다. 이후 리프 노드에 대해서는 리프든, 부모든 무조건 한 곳을 켜줘야 한다. 이 때 부모는 여러 리프를 가질 수 있으므로 부모 쪽을 키는 게 이득이다.

또한 리프와의 관계가 아닐 시에는 자식 노드가 켜져있는지 보고 만약 자식 모두가 켜져있는 게 아니면 부모 노드를 켜줘야 한다.

처음엔 부모와 자식들 간에서 자식 중에 하나라도 켜져 있으면 부모를 안 켜도 되는지 알았는데 각각 관계를 따져서 만약 하나의 자식이라도 안 켜져 있으면 부모를 켜줘야 한다.

 

#include <vector>

using namespace std;

vector<int> edge[100001];
int numCount=0;

//2은 리프노드, 1는 켜진 상태, 0은 꺼진 상태
int dfs(int parent, int node){
    if(parent!=0&&edge[node].size()==1) return 2;
    
    bool isOn = false;
    bool hasLeaf = false;
    
    for(int i = 0; i<edge[node].size(); i++){
        if(edge[node][i]==parent){
            continue;
        }
        int val = dfs(node, edge[node][i]);
        if(val==2){
            hasLeaf=true;
        }else if(val==0){
            isOn=true;
        }
    }
    if(hasLeaf||isOn) {
        numCount++;
        return 1;
    }else{
        return 0;
    }
}

int solution(int n, vector<vector<int>> lighthouse) {
    int answer = 0;
    
    for(int i = 0 ; i<lighthouse.size(); i++){
        edge[lighthouse[i][0]].push_back(lighthouse[i][1]);
        edge[lighthouse[i][1]].push_back(lighthouse[i][0]);
    }
    
    dfs(0, 1);
    
    answer = numCount;
    return answer;
}