[Algorithm] Programmers :: 등대

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

프로그래머스

vector<vector<int>> graph(100001);
bool visited[100001] = { false };
int answer = 0;
 
int DFS(int vertexNum)
{
    if (graph[vertexNum].size()-1 == 0)
    {
        return 0;
    }
 
    int count = 0;
    for (int i = 0; i < graph[vertexNum].size(); ++i)
    {
        int childVertex = graph[vertexNum][i];
 
        if (visited[childVertex] == false)
        {
            visited[childVertex] = true;
            count += DFS(childVertex);
        }
    }
 
    if (count == graph[vertexNum].size()-1) return 0;
 
    ++answer;
    return 1;
}
 
int solution(int n, vector<vector<int>> lighthouse) 
{
    for (int i = 0; i < lighthouse.size(); ++i)
    {
        int a = lighthouse[i][0];
        int b = lighthouse[i][1];
 
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
 
    visited[1] = true;
    int count = 0;
 
    for (int i = 0; i < graph[1].size(); ++i)
    {
        int childVertex = graph[1][i];
 
        if (visited[childVertex] == false)
        {
            visited[childVertex] = true;
            count += DFS(childVertex);
        }
    }
 
    if (count < graph[1].size()) ++answer;
    
    return answer;
}

 

문제 제대로 안읽고 순환그래프인줄 착각해서 헛고민에 상당히 빠졌던 문제.

문제에서 간선의 개수는 노드개수-1개, 즉 트리형태라고 설명이 되어있다.

 

결론만 말하자면, 자식노드가 하나라도 0이라면 반드시 자신(부모)는 등대를 켜야한다(1).

그렇다면 노드가 0이될 조건은 무엇인가... 가 다음 문제이다.

노드가 0이될 조건은 리프노드일 경우이다. 즉, 자식노드가 1개도 없을 때이다.

왜? 자식노드가 없기때문에 등대를 키는게 전혀 이득이 되지를 않는다. 

 

최소의 등대를 키려면 하나의 등대를 켰을 때 최대한 많이 다른 등대를 안키게 만드는게 중요한데, 리프노드에서 등대를 켜봤자 잘해야 부모노드만 안켜도되는 이득이 있을 뿐이다. 

근데 부모는 키는게 이득인 경우가 많다. 여러 자식을 거느린 부모의 경우, 부모가 킴으로써 자식은 안켜도 되는 상황이 있기 때문이다. 

하지만 리프노드는 그런경우가 없으니 무조건 안키는게 좋다. 

 

딱 위의 전제에서 문제해결이 시작된다. 

자식노드가 하나라도 0이라면(리프노드같은) 반드시 자신은(부모는) 켜야한다. 

왜? 문제조건(양 끝 노드중 한개는 반드시 켜야한다) 은 충족시켜야하니까.

 

그래서 리프노드같이 안켰을때는 부모에게 0을 리턴하고, 자식노드중 하나라도 0이여서 켰다면 부모에게 1을 리턴하는 식으로 작성했다. 그리고 누적값이 해당 노드랑 연결된 노드들의 개수 -1개와 누적값이 같다면 (즉, 자식들이 모두 켰다면) 부모에게 0을 리턴했다(자식들이 모두 켰으니 굳이 자기는 킬필요가 없다).