[백준] 4803번: 트리 - 무방향 그래프에서 DFS로 사이클 찾기

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

 

예제

6 3
1 2
2 3
3 4
6 5
1 2
2 3
3 4
4 5
5 6
6 6
1 2
2 3
1 3
4 5
5 6
6 4
0 0

---

ans : 
Case 1: A forest of 3 trees.
Case 2: There is one tree.
Case 3: No trees.

---

주어진 그래프에서 트리가 몇 개 존재하는지 판단하는 문제이다.

트리의 조건은 사이클이 없는 연결 요소이고 n-1개의 간선으로 이루어져 있고 임의의 두 정점에 대해 경로가 유일하다는 것인데, 이 조건을 이용해서 찾아야 한다.

처음에는 연결 요소를 찾고 사이클이 없는지 판단한 뒤 n-1개의 간선으로 이루어져 있고 모든 정점 간 경로가 유일한지 체크하려 했다. 그런데 bfs를 사용해서 연결 요소를 찾다 보니 탐색 과정에서 사이클을 판단할 수 있을 것 같다는 생각이 들었다. 심지어 나머지 조건은 사이클이 없는 것과 필요충분조건이라고 판단돼서 연결 요소를 찾으면서 사이클을 판단하는 방향으로 변경했다.

 

연결 요소를 찾는 방법은 DFS, BFS가 있다. 또, 사이클을 찾는 방법은 연결 요소를 쭉 찾으면서 인접 노드 중 부모가 아닌데 방문한 노드가 있다면 사이클이 존재한다고 판단할 수 있다. 쉽게 말하면 부모가 둘인 노드가 있으면 안되는 것이다. 

BFS라면 이렇게 ring을 그려가면서 방문할텐데 파란색 노드에서 사이클을 확인할 수 있을 것이고, DFS 또한 마찬가지로 부모가 아닌데 인접한 방문한 노드가 있으면 사이클이 존재하는 것이다.

 

BFS와 DFS 중 뭐가 더 빠를까를 고민해보면 평균적으로는 BFS가 더 빠르겠지만 운이 좋다면 (사이클이 있는 경로를 바로 방문하는 경우) DFS가 훨씬 빠를 것이다. 크게 차이가 없을 것이라 판단하고 구현이 더 쉬운 DFS로 판단했다. 

각 노드의 부모나 깊이를 체크할 필요가 없어서 가장 간단한 재귀형 DFS로 구현했다.

/** 트리 4803 트리 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
int n, m, tc = 0, ans = 0;
bool visited[520];
bool flag = true;
vector<int> g[510];

void dfs(int cur, int prev)
{
    for (int next : g[cur])
    {
        if (next == prev)
            continue;
        // dfs 도중 next가 부모가 아닌데 방문한 적 있다면 사이클이 있는 것이다.
        if (visited[next])
        {
            flag = false;
            // 해당 연결 요소가 트리가 아님을 알아도 dfs는 마저 끝내서 방문 표시를 마쳐야함
            continue;
        }
        visited[next] = true;
        dfs(next, cur);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    while (1)
    {
        cin >> n >> m;
        if (n == 0 && m == 0)
            break;

        fill(visited, visited + n + 1, false);
        for (int i = 1; i <= n; i++)
            g[i].clear();
        ans = 0;

        int u, v;
        for (int i = 0; i < m; i++)
        {
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }

        // 방문하지 않은 정점에 대해 dfs를 돌려서 연결 요소로 분리
        for (int node = 1; node <= n; node++)
        {
            if (visited[node])
                continue;
            flag = true;
            visited[node] = true;
            dfs(node, 0);
            ans += flag;
        }

        cout << "Case " << ++tc << ": ";
        if (!ans)
            cout << "No trees." << '\n';
        else if (ans == 1)
            cout << "There is one tree." << '\n';
        else
            cout << "A forest of " << ans << " trees." << '\n';
    }
}

 

트리에서는 재귀/비재귀, DFS/BFS를 많이 구현하므로 세 방식 모두 뇌에 잘 들어있어야 한다! 배열이나 그래프에서의 탐색과는 조금 다르다.