[백준] 4803 - 트리 (자바/Java)

문제 링크

성능 요약

메모리: 53236 KB, 시간: 408 ms

분류

자료 구조(data_structures), 깊이 우선 탐색(dfs), 분리 집합(disjoint_set), 그래프 이론(graphs), 그래프 탐색(graph_traversal), 트리(trees)

문제 설명

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

트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 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."를 테스트 케이스 번호와 함께 출력한다.

---

간단하다고 생각했는데 고려할 요소들이 생각보다 많았다.

놓쳤던 부분은 cycle이 존재하여도 tree가 존재한다면 tree의 개수를 출력해야 한다는 점이다.

그리고 출력에서 대소문자를 잘못 써서 틀린 이유를 찾아 헤맸다... (문제를 잘 읽자)

 

방문 여부를 체크하며 dfs를 진행하고, 이미 방문된 노드를 다시 방문할 경우 cycle이라고 체크하도록 하였다.

그런데 무방향 그래프니까, 1 2와 2 1을 모두 edge로 등록해줘야 한다. 이 때 1에서 2로 방문하여 다시 edge를 조사하는 경우, 2에서 1도 이어져있기 때문에 이를 cycle로 판단할 수 있다. 그래서 pre를 등록해서 해당 node의 edge 중, 이미 방문되었지만 node와 연결되어 있고, pre가 아닌 경우에는 cycle이 맞다고 판단하였다.

 

또 고려해야할 것은 1 1처럼 자기 자신으로 향하는 edge도 존재할 수 있다는 점이다. 이는 따로 pre와 edge가 같은 경우를 처리하여 cycle로 판단하였다.

 

package Gold.g4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_4803_트리 {
	static int N, M;
	static boolean visited[];
	static int[][] edges;
	static int cnt;
	static boolean cycle;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		edges = new int[501][501];
		int tc = 1;
		while (true) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			if (N == 0)
				break; // 0 종료 조건

			cycle = false;
			visited = new boolean[N + 1];
			for (int i = 1; i <= N; i++) {
				Arrays.fill(edges[i], 0);
			} // 순환할 때마다 edge 초기화

			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				int start = Integer.parseInt(st.nextToken());
				int end = Integer.parseInt(st.nextToken());
				edges[start][end] = 1;
				edges[end][start] = 1;
			} // 입력

			cnt = 0; // tree의 개수
			for (int i = 1; i <= N; i++) {
				if (!visited[i]) {
					cnt++;
					visited[i] = true;
					cycle = false;
					dfs(i, i);
					if (cycle)
						cnt--; // cycle이면 tree x
				}
			}
			sb.append("Case " + (tc++) + ": ");
			if (cnt == 0)
				sb.append("No trees.\n"); // 대문자로 잘못 씀.......................
			else if (cnt == 1)
				sb.append("There is one tree.\n");
			else
				sb.append("A forest of " + cnt + " trees.\n");
		}
		System.out.println(sb.toString());
	}

	static void dfs(int pre, int v) {
		for (int i = 1; i <= 500; i++) {
			if (edges[v][i] == 1) {
				if (visited[i] && i != pre || (v == i)) { // v==i인 경우는 1 1처럼 자기 자신으로 향하는 경우, i가 방문되었으나 이전 노드(부모 노드)가 아닌
															// 경우에는 cycle임
					cycle = true;
				}
				if (!visited[i]) {
					visited[i] = true;
					dfs(v, i);
				}
			}

		}
	}

}