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

 

 

문제

문제 설명

 

 

 

풀이

 

[문제 풀이]

 

이 문제는 주의해야하는 점이 A와 B 등대가 있다면 두 등대 중에 한 등대는 무조건 켜져있어야 한다는 점이다.

위 그림과 같이 등대가 켜져 있어도, A와 B 등대 사이에 불이 켜져있지 않기 때문에 정답이 될 수 없다.

A와 B 등대중 하나가 켜져있어야 된다.

 

이제 문제를 풀때 사이클이 없으므로 하나의 트리로 볼 수 있다.

이를 이용해 1을 트리의 최상단 노드라고 가정하고, leaf 노드를 찾는다.

여기서 leaf 노드를 찾을 경우 leaf 노드의 불을 켜는 것 보다 부모 노드의 불을 켜는게 더 좋다.

 

왜냐하면 leaf 노드는 연결된 노드가 하나이고, leaf 노드의 부모 노드는 최상단 노드인 1을 제외하면 연결된 노드가 적어도  2개 이상이기 때문이다. 그러므로 leaf 노드의 부모 노드를 켜는게 이득이다.

 

이제 여기서 BFS와 DFS로 풀 수 있다.

 

[BFS]

아래 그림을 참고하면 BFS로 풀 경우 주의해야 할 점은 다음과 같다.

leaf 노드일 경우 부모 노드를 킨다.

 

이후 현재 노드와 부모 노드의 연결을 해제하고 다시 부모 노드가 leaf 노드인지 확인해야한다.

위 그림에서 leaf노드의 부모인 Par노드를 킨 다음 연결을 끊고, Par 노드가 다시 leaf 노드인지 확인하면 Par 노드는 새 leaf 노드이다.

 

문제는 Par노드는 불이 켜져있기 때문에 부모 노드인 A노드를 킬 필요가 없다.

그러므로 Par노드와 부모노드인 A노드의 연결을 끊고 다시 A 노드가 leaf 노드인지 확인한다.

위 과정을 반복하며 현재 내 노드가 leaf 노드일 경우 불이 켜져있는지 꺼져있는지 확인해 내 부모 노드를 킬지를 결정하는 과정을 반복하는 것이다.

 

 

[DFS]

DFS로 풀 경우도 크게 다르지 않다.

 

DFS는 깊이 우선 탐색이므로 계속 자식노드들을 찾으며 탐색을 시작한다.

만약 자식 노드들과 자신 중 하나라도 불이 켜져있지 않다면 자신의 불을 키면 된다.

 

예를 들어 A노드의 자식노드가 (B, C, D)가 있다고 가정하자

이 경우 A 노드는 B, C, D 노드가 켜져있는지 확인한다.

물론 B, C, D 노드도 B, C, D 노드의 자식들과 자신을 비교하며 둘 중 하나라도 켜져있지 않은 경우가 있는지 확인해야한다.

즉, 이 경우를 반복하면 맨 아래 leaf 노드는 자식이 없으므로 불이 꺼져있게 된다. leaf노드의 부모 노드는 leaf노드와 비교하고 leaf노드가 꺼져있으므로 불을 킨다. 

 

그림으로 DFS과정을 보면 다음과 같다.

 

 

위 그림에서 DFS로 A 탐색을 시작한다. 이후 자식 노드인  B를 탐색하고 B도 다시 DFS로 자식 노드인 E를 탐색한다.

여기서 E노드는 자식이 없으므로 탐색을 종료하고 다시 B로 넘어가서 B와 E를 비교한다.

여기서 자식노드인 E가 불이 꺼져 있으므로 B의 불을 킨다.

 

마찬가지로 B도 탐색을 마쳤으므로 A로 돌아가 다음 자식인 C를 탐색하는 과정을 반복하면 B와 C는 불이 켜지게 된다.

D의 경우는 자식 노드가 없으므로 탐색을 종료하고, A 노드로 돌아간다.

A노드와 D노드를 비교할 때, 둘 다 켜져있지 않으므로 A노드를 킨다.

 

요약하면 DFS와 BFS 둘 다 Leaf노드를 찾아서 부모 노드와 비교하고 불을 켤지 말지를 결정하는 과정인데, leaf노드를 찾는게 DFS인지, BFS인지 차이다.

​

[아이디어 정리]

1. 하나의 노드를 최상위 노드로 정해 트리 구조로 본다.
2. leaf노드와 부모노드의 관계를 비교하고 둘 다 불이 꺼져있는 상태라면, 부모노드를 킨다.
3. 위 과정을 반복해 불이 켜진 등대 수를 return한다.

 

Code (BFS)

 

 

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int n, vector<vector<int>> lighthouse) {
    int answer = 0;
    // 항상 1번 노드가 루트 노드
    vector<vector<int>> tree(n+1);
    vector<int> parents(n+1,0);
    vector<int> isLeaf(n+1,0);
    for (int i=0; i<n-1; i++){
        tree[lighthouse[i][0]].push_back(lighthouse[i][1]);
        tree[lighthouse[i][1]].push_back(lighthouse[i][0]);
        isLeaf[lighthouse[i][1]]+=1;
        isLeaf[lighthouse[i][0]]+=1;
    }
    int stNode=1;
    parents[1]=1;
    queue<int> q,leafQ;
    q.push(1);
    vector<bool> visited(n+1,false);
    for (int i=2; i<tree.size(); i++)
    {
        if (isLeaf[i]==1)
        {
            leafQ.push(i);
        }
    }
    int ppN=1;
    queue<int> qqq;
    qqq.push(ppN);
    while(!qqq.empty())
    {
        ppN=qqq.front();
        qqq.pop();
        for(int i=0; i<tree[ppN].size(); i++)
        {
            if (parents[tree[ppN][i]]==0)
            {
                parents[tree[ppN][i]]=ppN;
                qqq.push(tree[ppN][i]);
            }
        }
    }    
    // 부모와 나 중 하나는 반드시 켜져야함, 그런데 내가 꺼져있으면 부모를 키는게 맞다.
    while (!leafQ.empty())
    { //leaf라면 상위노드는 무조건 방문 해야함
        int nowLeaf=leafQ.front();
        leafQ.pop();
        int parNode=parents[nowLeaf];
        if (nowLeaf!=1)
        {
            if (!visited[nowLeaf] && !visited[parNode])
            { //하나라도 방문 했다면 등대 길이 켜져있는 것이므로 pass
                if (isLeaf[nowLeaf]==1)
                {        
                    visited[parNode]=true; // 방문처리
                    answer+=1;
                } 
            }
            if (isLeaf[nowLeaf]==1) // 현재 노드가 leaf노드인지 확인
            {
                isLeaf[nowLeaf]-=1;
                isLeaf[parNode]-=1;
                leafQ.push(parNode);
            }
        }
    } 
    return answer;
}

 

 

Code (DFS)

 

 

#include <string>
#include <vector>
#include <queue>

using namespace std;
vector<vector<int>> tree;
vector<bool> visited;
int retAns=0;
void DFS(int nowNode, int parNode)
{
    for (int i=0; i<tree[nowNode].size(); i++)
    {
        if (tree[nowNode][i]!=parNode)
        {
            DFS(tree[nowNode][i],nowNode);
            if (!visited[nowNode]&&!visited[tree[nowNode][i]])
            {
                visited[nowNode]=true;
                retAns+=1;
            }
        }        
    }    
}

int solution(int n, vector<vector<int>> lighthouse) {
    tree=vector<vector<int>>(n+1);
    visited=vector<bool>(n+1,false);
    vector<int> parents(n+1,0);
    for (int i=0; i<lighthouse.size(); i++){
        tree[lighthouse[i][0]].push_back(lighthouse[i][1]);
        tree[lighthouse[i][1]].push_back(lighthouse[i][0]);
    }
    DFS(1,1);
    return retAns;
}

---

 

처음에 BFS로 푸는데, 아무리 생각해도 안 풀려서 이해가 안됐다.

2시간 넘게 고민했는데... 나중에 생각해보니 부모노드가 Leaf 노드인지 확인을 안하고 바로 queue에 넣어서 실행해 버린게 문제였다;;

DFS로 풀면 관계를 끊을 필요 없이 그냥 탐색하면 되는데 괜히 고생했다;;;

 

프로그래머스