[백준 BOJ/C++] 4803 트리

 

4803번: 트리

 

기본적인 사이클 탐지 알고리즘 문제다.
그래프(Graph) 내에서 사이클(Cycle) 이 존재하는지를 찾는 문제는 흔한 그래프 탐색 문제 유형 중 하나다.

 

 

이 문제에서는 트리(Tree) 의 정의를 이용해서 주어진 그래프 내에서 사이클이 존재하는지 확인하고 사이클을 이루는 노드들에 연결되지 않은 트리의 수를 찾아야 한다.

 

 

트리는 그래프의 한 종류로 그래프가 트리가 되기 위해서는 몇가지 조건이 있지만 이 문제에서는 사이클만 신경써주면 된다.

문제에서 입력 자체가 두 노드 사이에 간선은 하나만 주어지고 간선에 가중치가 있는것도 아니기 때문에 사이클의 존재 여부로만 트리인지 아닌지 판단할 수 있다.

 

 

단, 주의해야하는 점은 예제로 주어진 입력과 같이 주어지는 간선정보에 포함되지 않은, 다른 노드와 연결되지 않은 노드들도 존재한다는 것이며 이런 노드들도 각각 노드가 하나인 트리로 카운트해주어야 한다는 점이다.

 

 

---

 

 

문제의 포인트

 

사이클 탐지 알고리즘
테스트 케이스가 여러개인 그래프 문제의 처리

 

 

사이클 탐지 알고리즘

 

그림은 문제의 기본 예시에 주어지는 3가지 그래프들이다.

이렇게 그림으로 그려보면 판별 기준을 쉽게 정리해볼 수 있다.

 

 

2668번: 숫자고르기 문제와 같이 그래프 내에서 한 노드 씩 DFS를 통해 인접한 노드들을 탐색하다가 이미 방문했던 노드를 만났을 때 사이클로 판단하면 된다.

조금 다른점은 이 문제에서는 사이클에 속하는 노드들의 수를 찾거나 그 노드들을 특정할 필요는 없기 때문에 사이클을 따라서 한번 더 탐색해줄 필요는 없다.

사이클이 없는 트리를 찾아야 하기 때문에 반대의 개념으로 결과를 취합해주면 된다.

 

 

재귀함수를 이용해 DFS를 구현한 경우 중복 방문한 노드를 만나는 순간 return 처리와 같은 방법으로 간단히 사이클 존재 여부만 확인해주면 된다.

 

 

단, 실수가 발생하기 쉬운 부분이 바로 이 DFS에서의 return 처리인데, 현재 탐색할 노드에서 사이클이 발견되었다 하더라도 탐색중인 그래프에 연결된 노드들은 끝까지 탐색해줘야 하기 때문에 인접 노드들을 탐색하기 위한 for문에서 완전히 빠져나와선 안된다.

이부분만 주의한다면 그래프 내에서 중복 방문 여부만 확인해서 트리인지 아닌지 판단해주면 된다.

 

 

테스트 케이스가 여러개인 그래프 문제의 처리

 

이 문제는 테스트 케이스가 여러개이며 매 테스트 케이스마다 주어지는 그래프가 바뀐다.

따라서 그래프를 표현한 인접 리스트와 visit 배열 등의 data들을 각 TC 마다 초기화해주는 것을 잊지 않아야 한다.

 

 

별것 아닌 문제 같지만 필요한 자료구조를 제대로 초기화 하지 않는 경우 엉뚱한 부분에서 원인을 못찾고 헤맬 수 있다.

특히 인접리스트와 같이 리스트 형태로 데이터를 push back 해서 이어주면서 또 이것을 여러개 배열로 관리해야 하는 경우 이 리스트 배열을 확실히 clear 해주어야 한다.

 

 

그래프 문제 중 이처럼 테스트 케이스가 여러개고 매번 새로운 그래프를 입력받아야 한다면 그래프를 표현해주는 인접 리스트의 초기화에 대해서 항상 신경써야 한다.

 

 

---

 

 

전체 Code

 

#include <iostream>
#include <vector>

using namespace std;

int N, M;
vector<int> adj[500 + 10];
int visit[500 + 10];

void clearTree() {
	int i;
	for (i = 1; i <= N; i++) {
		adj[i].clear();
		visit[i] = 0;
	}
}

int DFS(int n, int prev) {

	visit[n] = 1;

	for (auto next : adj[n]) {
		if (next == prev) continue;

		if (visit[next])
			return 0;

		if (DFS(next, n) == 0)
			return 0;
	}
	return 1;
}

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

	int t, i, a, b, tree_cnt;
	t = 0;

	while(1) {
		t++;
		cin >> N >> M;
		if (N == 0 && M == 0)
			break;

		tree_cnt = 0;
		for (i = 0; i < M; i++){
			cin >> a >> b;
			adj[a].push_back(b);
			adj[b].push_back(a);
		}

		for (i = 1; i <= N; i++) {
			if (visit[i] == 0) {
				if (DFS(i, 0))
					tree_cnt++;
			}
		}
		cout << "Case " << t << ": ";
		if (tree_cnt == 0) {
			cout << "No trees.\n";
		}
		else if (tree_cnt == 1) {
			cout << "There is one tree.\n";
		}
		else {
			cout << "A forest of " << tree_cnt << " trees.\n";
		}

		clearTree();
	}

	return 0;
}