[백준] 트리(4803)

문제

[백준] 트리(4803)

그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.

트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해서 경로가 유일하다.

그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n ≤ 500과 m ≤ n(n-1)/2을 만족하는 정점의 개수 n과 간선의 개수 m이 주어진다. 다음 m개의 줄에는 간선을 나타내는 두 개의 정수가 주어진다. 같은 간선은 여러 번 주어지지 않는다. 정점은 1번부터 n번까지 번호가 매겨져 있다. 입력의 마지막 줄에는 0이 두 개 주어진다.

출력

입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다.

해설

문제에 나와 있듯이 트리의 정점이 n개, 간선이 n-1개라는 특성을 적용해 풀이할 수 있다.

2차원 배열 graph를 만들어 연결된 노드를 저장한 뒤(무방향), 방문처리 안 된 정점을 BFS로 탐색하여 사이클이 존재하는지 확인한다. 여기서 싸이클 존재 여부가 트리의 특성이 되는데 무방향 그래프로 간선을 저장했기 때문에 정점 A와 B를 연결하는 간선은 graph[A][B]와 graph[B][A] 두 가지이다.

즉, 간선이 두 배가 되므로 연결된 간선을 2로 나누어 주어야 한다.

또한, 인접리스트를 사용했을 때 보다 인접행렬을 사용했을 때 시간과 메모리가 적게 들었다.

풀이

import java.util.*;
import java.io.*;


public class Main {
	static boolean[][] graph;
	static boolean[] visited;
	static int answer;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		int n = 0, m = 0, count = 0;

		while (true) {
			count++;
			st = new StringTokenizer(br.readLine(), " ");

			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());

			if (n == 0 && m == 0)
				break;

			sb.append("Case ").append(count).append(": ");

			graph = new boolean[n][n];
			visited = new boolean[n];

			for (int i = 0; i < m; i++) {
				st = new StringTokenizer(br.readLine(), " ");

				int a = Integer.parseInt(st.nextToken()) - 1;
				int b = Integer.parseInt(st.nextToken()) - 1;

				graph[a][b] = true;
				graph[b][a] = true;
			}

			answer = 0;

			for (int i = 0; i < n; i++) {
				if (!visited[i]) {
					visited[i] = true;
					bfs(i);
				}
			}

			if (answer == 0)
				sb.append("No trees.");
			else if (answer == 1)
				sb.append("There is one tree.");
			else
				sb.append("A forest of ").append(answer).append(" trees.");

			sb.append("\n");
		}

		System.out.println(sb.toString());
	}

	public static void bfs(int u) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(u);

		int edge = 0, node = 0;

		while (!queue.isEmpty()) {
			int nowV = queue.poll();
			node++;

			for (int v = 0; v < graph[nowV].length; v++) {
				if(graph[nowV][v]) {
					edge++;
					
					if (!visited[v]) {
						visited[v] = true;
						queue.add(v);
					}
				}
			}
		}

		if (edge / 2 == node - 1)
			answer++;
	}
}