백준 - 4803 트리(Java)

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

4803번: 트리

 

트리 문제입니다.

테스트 케이스마다 그래프가 주어지고, 해당 그래프에 트리가 몇 개인지 출력을 하는 문제입니다.

 

트리는 부모-자식이 계층 구조를 가지는 비선형 자료구조입니다.

계층 구조를 지니기 때문에, 사이틀이 발생해서는 안됩니다.

 

위 그림과 같이, 트리는 그래프와 달리 사이클이 생기면 안됩니다.

 

두 개의 노드를 연결하는 트리의 간선 개수는 몇개 일까요? 네, 1개 입니다.

세 개의 노드를 연결하는 트리의 간선 개수는 몇개 일까요? 네, 2개 입니다.

네 개의 노드를 연결하는 트리의 간선 개수는 몇개 일까요? 네, 3개 입니다.

 

눈치 채셨나요? 이진 트리의 노드와 간선의 관계를 말이죠.

노드를 N, 간선을 E라고 하면 N = E+1의 공식이 발생합니다.

 

이 성질을 이용해 방문하지 않은 노드를 확인하면서 트리의 개수를 세면 됩니다.

이전에 방문한 노드는 트리이거나 그래프로 이미 판별이 났기 때문에 확인을 하지 않습니다.

 

[구현 코드]

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

public class Main {
    static List<ArrayList<Integer>> graph;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz;

        int testCase = 1;

        while (true) {
            stz = new StringTokenizer(br.readLine(), " ");

            int n = Integer.parseInt(stz.nextToken());
            int m = Integer.parseInt(stz.nextToken());

            // 0 0이면 종료
            if (n == 0 && m == 0) break;

            graph = new ArrayList<>();
            for (int i = 0; i < n + 1; i++) {
                graph.add(new ArrayList<>());
            }

            visited = new boolean[n + 1];

            // 입력값으로 그래프를 만듦
            for (int i = 0; i < m; i++) {
                stz = new StringTokenizer(br.readLine(), " ");
                int a = Integer.parseInt(stz.nextToken());
                int b = Integer.parseInt(stz.nextToken());

                graph.get(a).add(b);
                graph.get(b).add(a);
            }

            // 아직 방문하지 않은 노드들을 확인해 트리인지 확인
            // 루트 노드만 있어도 트리임
            int tree = 0;
            for (int i = 1; i < n + 1; i++) {
                if (!visited[i]) {
                    tree += checkTree(i);
                }
            }
            bw.write("Case " + testCase + ": ");

            if (tree > 1) {
                bw.write("A forest of " + tree + " trees.");
            } else if (tree == 1) {
                bw.write("There is one tree.");
            } else {
                bw.write("No trees.");
            }
            bw.write("\n");

            testCase++;
        }

        bw.flush();
        bw.close();
        br.close();
    }

    // 트리일 경우 n = e+1
    private static int checkTree(int root) {
        Queue<Integer> qu = new LinkedList<>();
        int node = 0;
        int edge = 0;

        qu.add(root);

        while (!qu.isEmpty()) {
            int cn = qu.poll();

            if (visited[cn]) continue;
            visited[cn] = true;
            node++;

            for (int i = 0; i < graph.get(cn).size(); i++) {
                int nn = graph.get(cn).get(i);
                edge++;
                if (!visited[nn]) {
                    qu.add(nn);
                }
            }
        }

        // 무방향 그래프 이므로 (e/2)해야 함
        return (edge / 2) + 1 == node ? 1 : 0;
    }
}