[백준/C++] Tree (No. 13244)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 트리의 특징을 잘 알고있으면 쉽게 풀 수 있는 문제다.

 

먼저 트리의 특징은 사이클이 없고, 한 노드에서 경로를 따라 다른 모든 노드에 방문할 수 있어야한다는 점이 있다.

 

그러므로 이러한 조건을 만족하는 경우를 찾아 tree인지 graph인지 출력하면 되는 문제다.

 

먼저 트리의 특징을 이용하면 쉽게 N과 M의 수를 이용해 트리인지 그래프인지 판단할 수 있다.

트리는 노드의 개수가 N일 때 경로(간선)의 개수가 N-1이라는 특징이 있다.

 

만약 경로가 N-1보다 크다면, 사이클이 무조건 존재하게 된다.

경로가 N-1 보다 작다면, 한 노드에서 방문할 수 없는 노드가 존재하게 된다.

 

그러므로 위 조건을 참고해 N과 M이 M = N-1의 관계일 때만 사이클이 존재하는지 판단하면 된다.

 

풀이 방법은 다양한다.

 

첫 풀이 방법은 노드를 하나 정한 뒤 BFS로 경로를 따라 탐색하는 방법이다.

이때, A노드에서 B노드를 방문하면 A노드는 B 노드의 상위노드(부모노드) 임을 표시했다. 

 

fig1

 

위 그림의 빨간 노드에서 탐색을 시작한다고 생각해보자

 

1번의 경우는 빨간 노드를 기준으로 하위노드를 탐색해 나가면 빨간 노드와 연결된 노드의 개수가 5개이며, 사이클이 없다는 것을 알 수 있다.

 

2번의 경우는 빨간 노드를 기준으로 하위노드를 탐색해 나가면 빨간 노드와 연결된 노드의 개수가 2개이기 때문에 트리가 아님을 알 수 있다.

 

3번의 경우는 빨간 노드를 기준으로 탐색해 나가면 사이클이 있음을 알 수 있다.

(왼쪽 노드와 오른쪽 노드의 부모노드는 빨간 노드인데, 왼쪽 노드와 오른쪽 노드가 연결되어있어 왼쪽 노드에서 오른쪽 노드로 탐색을 하게 되면 이미 부모노드가 존재한다는 것을 이용해 사이클임을 알 수 있다)

 

두번째 풀이방법은 Union Find를 이용하는 것이다.

 

Union Find는 서로 다른 집합을 하나의 집합으로 합치는 알고리즘이다.

 

A노드가 속한 집합과 B노드가 속한 집합이 있을 때, 두 집합이 같다면 두 노드는 연결된 것이다.

만약 특정 두 노드의 집합을 합치려고하는데, 이미 두 노드가 같은 집합에 있다면, 사이클이 존재한다는 것을 알 수 있다.

 

이를 이용해 트리인지 아닌지 쉽게 알 수 있다.

 

 

 

[아이디어 정리]

1. 노드의 개수 N과 간선의 수 M이 M=N-1 관계일 때만 트리를 만들 수 있다.
2. 한 노드를 최상위 노드로 정하고 BFS 탐색해 실제로 트리인지 아닌지 판단한다.
3. 다른 방법으로는 Union Find 알고리즘으로 두 노드가 이미 같은 집합에 속해 있는지를 판단하고 사이클을 찾아 트리인지 아닌지 판단한다.

 

 

 

Code (BFS)

 

 

 

#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

void Calc(int N, int M)
{
    int a, b;
    if (N - 1 != M) {
        for (int i = 0; i < M; i++) {
            cin >> a >> b;
        }
        cout << "graph\n";
        return;
    }
    vector<vector<int>> road(N + 1, vector<int>(0));
    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        road[a].push_back(b);
        road[b].push_back(a);
    }
    vector<int> parents(N + 1, 0);
    queue<int> q;
    int cnt = 1;
    q.push(1);
    while (!q.empty())
    {
        a = q.front();
        q.pop();
        for (int i = 0; i < road[a].size(); i++) {
            b = road[a][i];
            if (b != parents[a])
            {
                if (parents[b] != 0) {
                    cout << "graph\n";
                    return;
                }
                parents[b] = a;
                q.push(b);
                cnt += 1;
            }
        }
    }
    if (cnt == N)
        cout << "tree\n";
    else
        cout << "graph\n";
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int TC, N, M; //M은 캐릭
    cin >> TC;
    for (int tc = 0; tc < TC; tc++) {
        cin >> N >> M;
        Calc(N,M);
    }
   
    return 0;
}

 

 

Code (Union Find)

 

 

 

#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int unionFind(vector<int> &vSet, int num)
{
    if (vSet[num] == num) {
        return num;
    }
    return vSet[num] = unionFind(vSet, vSet[num]);
}

void Calc(int N, int M)
{
    int a, b, ap, bp;
    if (N - 1 != M) {
        for (int i = 0; i < M; i++) {
            cin >> a >> b;
        }
        cout << "graph\n";
        return;
    }
    vector<int> vSet(N + 1, 0);
    for (int i = 1; i < vSet.size(); i++)
        vSet[i] = i;
    bool flag = true;
    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        if (flag)
        {
            ap = unionFind(vSet, a), bp = unionFind(vSet, b);
            if (ap == bp) {
                flag = false;
            }
            vSet[ap] = bp;
        }
    }
    if (flag)
        cout << "tree\n";
    else
        cout << "graph\n";
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int TC, N, M;
    cin >> TC;
    for (int tc = 0; tc < TC; tc++) {
        cin >> N >> M;
        Calc(N,M);
    }
   
    return 0;
}

---

 

트리의 특징에 대해 잘 생각해보면 쉽게 풀이방법을 생각할 수 있는 문제였다.

 

 

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