백준 4803번: 트리 (C++)

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

풀이방법

개인적으로 문제를 푸는데 어려움이 있었다.. 첫 번째 이유는 문제가 잘 이해가 안 갔고, 두번째로 문제를 이해하고 나서 구현 방법 자체가 헷갈렸다.

첫 번째로 해당 문제를 이해하자면 n개의 정점으로 이루어진 그래프가 여러 개 존재하게 되는데 그 그래프 중에서 트리 형태의 그래프가 몇 개인지 맞추는 문제라고 볼 수 있다 이해가 안 가면 예시 입력을 바탕으로 그림을 그려보면 쉽게 이해가 갈 것이다.

두 번째로 구현 자체가 어려웠는데 bfs를 만들어서 풀 수 있다. 여기서 가장 중요한 포인트는 아래 코드 중에서 bfs함수 안쪽을 보면 if (nxt == prev) continue;의 의미는 bfs탐색 할 때 트리 같은 경우는 루트부터 시작해서 자식 방향으로 탐색하므로 부모는 이미 탐색 되었으므로 탐색할 필요가 없기 때문에 필요한 코드다.

그리고 가장 중요한 부분인 if (vis[nxt]) 경우이다 vis[nxt]가 만약에 true라면 사실상 부모 위의 어딘가로 재 방문 했다는 의미다. 즉 간선이 부모 위의 어딘가로 다시 연결되었다는 의미이기 때문에 순환 구조가 된다. 따라서 해당 그래프는 트리가 아니게 된다. 그런 경우에는 isTree라는 변수를 false로 바꿔주고 continue로 다음 것을 탐색한다. 위 원리만 이해한다면 아래 코드를 이해하는데 문제가 없을 것이다.

코드

#include <bits/stdc++.h>
using namespace std;


vector<int> adj[505];
int vis[505], isTree;
int n, m, u, v, tc, trees;


void dfs(int cur, int prev)
{
	for (auto nxt : adj[cur])
	{
		if (nxt == prev) continue; // next가 부모(prev)일 경우 건너뜀
		if (vis[nxt]) // 트리일 경우 자식은 반드시 이전에 방문한 적이 없었어야 하고, 이전에 방문을 했다면 현재 보고 있는 connected component가 트리가 아님을 의미
		{
			isTree = false;
			continue;
		}
		vis[nxt] = true;
		dfs(nxt, cur);
	}
}


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

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


		fill(vis, vis + n + 1, 0);
		for (int i = 1; i <= n; i++) adj[i].clear();
		trees = 0;

		while(m--)
		{
			cin >> u >> v;
			adj[u].push_back(v);
			adj[v].push_back(u);
		}

		for (int i = 1; i <= n; i++)
		{
			if (vis[i]) continue;
			vis[i] = true;
			isTree = true;
			dfs(i, -1);
			trees += isTree;
		}
		
		cout << "Case " << ++tc;
		if (trees == 0)
		{
			cout <<  ": No trees." << '\n';
		}
		else if (trees == 1)
		{
			cout <<  ": There is one tree." << '\n';
		}
		else
		{
			cout <<  ": A forest of " << trees << " trees." << '\n';
		}

	} 
}