[백준 6416 C++][G5] 트리인가?

⭐️ 난이도

Gold 5

---

⭐️ 문제

https://www.acmicpc.net/problem/6416

6416번: 트리인가?

 

 

---

⭐️ Idea flow

 

우선 input에서 정점이 몇 개 있는지 알려주지 않는다.

대신 간선의 정보를 입력 받으면서 연결되는 두 정점의 번호와 정점의 개수를 알 수 있다.

 

정점의 개수를 미리 알 수 없으니 배열이나 vector를 선언하여 미리 할당하는 것이 불가능하다.

따라서 unordered_map<int, vector<int>> edge를 선언하여 key에는 시작하는 정점의 번호, value(vector<int>)에는 도착하는 정점의 번호를 저장한다.

 

문제에 써져 있는 조건을 간단히 보면 들어오는 간선이 하나도 없는 노드가 단 하나 있어야 하고, 이를 root 노드라고 한다.

또한 root 노드에서 다른 모든 노드로 가는 경로가 단 하나여야 한다.

 

따라서 root 노드에서 BFS를 실행 했을 때

1) 검사하는 도중에 이미 방문한 노드를 다시 방문하면 안되며

2) root 노드를 제외한 모든 노드에 도달해야 한다.

 

그렇다면 root는 노드는 어떻게 찾을 것인가?

root 노드는 들어오는 간선이 하나도 없어야 한다. 그러므로 간선의 정보(u->v)를 받을 때, v 값만 set에 insert한다.

그리고 edge에 들어있는 값의 first가 set에 있는지의 유무를 확인한다.

set에 해당 값이 없다는 뜻은 들어오는 간선이 하나도 없다는 뜻이고, 이 말은 곧 root 노드가 된다는 뜻이다.

하지만 root 노드는 반드시 하나여야 하기 때문에 edge[i].first에 있는 값들을 모두 확인하고 만일 하나 이상이라면

해당 케이스는 트리가 아니다.

 

전체적인 알고리즘을 보면

1. 간선 정보를 받으면서 edge에 간선 정보 추가, vertex에 간선이 꽃히는 노드 정보 추가, isVisited에 등장하는 노드의 정보 추가

2. root 노드를 찾는다. 만일 root 노드가 2개 이상이면 트리가 아니다.

3. BFS를 통해 root와 이어진 노드들까지 중복 방문 없는 루트가 있는지 확인

4. 모든 노드들 중에 방문하지 않은 노드가 없는지 확인

   아직 방문하지 않은 노드가 있다는 것은 root와 이어지지 않았다는 뜻이고, 곧 root에서 해당 노드까지 루트가 존재하지 않는다는 뜻이다.

 

 

---

⭐️ Code

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <unordered_set>
#include <unordered_map>

#define INF 987654321
#define MAX 1000000 + 1
using namespace std;

// 6416 - 트리인가?

int find_root(unordered_set<int>& vertex, unordered_map<int, vector<int>>& edge){
    // root 노드란 들어오는 간선이 하나도 없는 노드이므로
    // vertex set에 해당 값이 존재하지 않으면 root 노드이다.
    int root = 0, cnt = 0;
    for(auto iter = edge.begin(); iter != edge.end(); iter++){
        if(vertex.count(iter->first) == 0){
            root = iter->first;
            cnt++;
            if(cnt >= 2){
                return -1; // root가 여러 개 존재
            }
        }
    }
    return root;
}

bool BFS(unordered_map<int, vector<int>>& edge, unordered_map<int, int>& isVisited, int root){
    queue<int> q;
    q.push(root);
    isVisited[root] = 1;

    while(!q.empty()){
        int cur = q.front();
        q.pop();

        for(int i = 0; i < edge[cur].size(); i++){
            int next = edge[cur][i];
            if(isVisited[next] == 0){ // 아직 방문한 곳이 아닌 경우
                isVisited[next] = 1;
                q.push(next);
            }
            else{
                return false;
            }
        }
    }
    return true;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int testcase = 0;

    while(true){
        unordered_map<int, vector<int>> edge;
        unordered_map<int, int> isVisited; // key: node, second: isVisited(0:no, 1:yes)
        unordered_set<int> vertex;
        int u = 1, v = 1;
        bool isTree = false;
        testcase++;

        while(true){
            cin >> u >> v;
            if(u == -1 && v == -1)  return 0;
            if(u == 0 && v == 0)    break;

            edge[u].emplace_back(v); // u -> v 간선
            vertex.insert(v); // 들어오는 간선이 있는 정점 체크
            if(isVisited.count(u) == 0) isVisited[u] = 0;
            if(isVisited.count(v) == 0) isVisited[v] = 0;
        }

        int root = find_root(vertex, edge); // root 노드를 찾는다.
        if(root == -1){
            cout << "Case " << testcase <<" is not a tree." << '\n';
            continue;
        }
        else{
            if(BFS(edge, isVisited, root))
                isTree = true;
        }

        // 방문하지 않은 노드가 있는지 확인
        for(auto iter = isVisited.begin(); iter != isVisited.end(); iter++){
            if(iter->second == 0){ // 방문하지 않은 노드가 있다면 조건 충족 X
                isTree = false;
                break;
            }
        }

        if(isTree){
            cout << "Case " << testcase <<" is a tree." << '\n';
        }
        else{
            cout << "Case " << testcase <<" is not a tree." << '\n';
        }
    }
}

 

---

⭐️ Feedback

 

대부분의 문제에서 정점의 개수 대한 정보가 주어지는데, 이번 문제에서는 정점의 개수에 대한 정보가 주어지지 않았다.

그래서 바로 map이나 set과 같은 연관 컨테이너를 쓸 생각을 하긴 했는데, 이를 어떻게 활용해야 할지 처음엔 생각이 나지 않았다.

 

구글링을 통해 map의 value에 다른 컨테이너를 쓸 수 있다는 것을 알게 되었고 이를 바탕으로 문제를 해결할 수 있었다.