[백준/C++] 트리

문제

문제 설명

 

 

풀이

 

[문제 풀이]

이 문제는 트리가 몇 개인지 세면 되는 문제다.

 

여기서 트리의 특징은 사이클이 존재하지 않는다는게 특징이다.

문제에서는 연결된 간선에 없이 하나의 노드만 있는 경우도 트리로 세기 때문에 사이클이 있는지만 검사하면 쉽게 풀 수 있는 문제다.

 

사이클을 찾는 방법은 쉽다.

 

특정 노드를 루트 노드로 정한 뒤 그 노드를 시작으로 트리를 탐색한다.

그러면 모든 노드는 부모 노드가 정해지게 된다.

 

이렇게 탐색할 때, B노드의 자식인 A노드에 부모노드가 정해져있다면, 사이클이 존재하는 것이다.

 

아래 그림을 통해 더 쉽게 알아보자

왼쪽은 정상적으로 트리를 탐색했을 경우다.
부모노드인 P의 값이 정상적으로 저장되는 모습을 볼 수 있다.

 

반대로 오른쪽은 사이클이 있는 경우다.

1번 노드에서 시작했고, 2번 노드의 차례에서 부모노드가 아니면서 연결된 노드가 3, 4 이므로 3, 4번 노드에 부모 노드가 2라는 정보를 저장한다.

 

문제는 이후에 3번 노드를 탐색하는 과정에서 생긴다.

3번 노드에서 부모가 아니면서 연결된 노드에는 4번이 있는데, 이미 4번에는 부모가 2번 노드라는 정보가 저장되어 있다.

그러므로 이 경우 사이클이 존재한다는 뜻이므로 1번 노드와 연결된 그래프는 트리가 아니라는 사실을 알 수 있다.

 

위와 같은 방법으로 특정 트리의 사이클이 존재하는지 판단하면 된다.

 

이때 트리가 여러개 있을 수 있으므로 for문으로 부모노드가 정해지지 않은 노드가 있으면 트리를 그리도록 코드를 구현했다.

 

 

​

[아이디어 정리]

1. 부모가 정해지지 않은 노드면 아직 그 노드와 연결된 그래프는 탐색하지 않았으므로 그 노드를 루트 노드로 하는 트리를 그리며 탐색을 시작한다.
2. 트리를 탐색할 때, 자식 노드 중 이미 부모가 정해진 노드가 존재한다면, 사이클이 존재한다는 뜻이므로 트리가 아니다.
3. 모든 노드를 검사한 후, 존재하는 트리의 수에 따라 정답을 출력한다.

 

 

 

 

Code

 

 

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


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);
	int n, m;
	int T=0, tc=1;
	while (true) {
		cin >> n >> m;
		if (n == 0 && m == 0) {
			break;
		}
		vector<int> par(n + 1,0);
		vector<vector<int>>graph(n + 1);
		int a, b;
		for (int i=0; i<m ;i++){
			cin >> a >> b;
			graph[a].push_back(b);
			graph[b].push_back(a);
		}

		for (int i = 1; i <= n; i++) {
			if (par[i] == 0) {
				// 탐색 시작
				queue<int> q; // nowNode, prevNode;
				par[i] = i;
				bool flag = true;
				q.push(i);
				int nowN;
				while (!q.empty()) 
				{
					nowN = q.front();
					q.pop();
					for (int j = 0; j < graph[nowN].size(); j++) {
						int nextN = graph[nowN][j];
						if (nextN !=par[nowN]) {
							if (par[nextN] == 0) {
								par[nextN] = nowN;
								q.push(nextN);
							}
							else {
								flag = false;
							}
						}
					}
				}
				if (flag) {
					T++;
				}
			}
		}

		cout << "Case " << tc << ": ";
		if (T == 0) {
			cout << "No trees.\n";
		}
		else if (T == 1) {
			cout << "There is one tree.\n";
		}
		else {
			cout << "A forest of " << T << " trees.\n";
		}
		T = 0;
		tc++;
	}
	return 0;
}

 

---

트리의 특징을 알고 있다면 사이클을 찾는 방법을 이용해 빠르게 풀 수 있는 문제다.

 

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