[백준 4803] 트리 / 자바 / bfs

#문제         

레벨: G4
알고리즘: bfs 
풀이시간: 40분
힌트 참조 유무:

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

---

#문제 풀이        

 

이 문제는 트리와 그래프를 구별할 수 있냐 없냐이다.

트리의 간선 개수는 노드-1이다. 그래프의 간선 개수는 노드개수보다 많다. 

 

그래서 우린 노드와 간선의 개수를 비교해서 트리를 구별해야한다. 

그 노드를 방문 했든 안했던 해당 노드와 이어져 있는 노드의 간선들을 더한다. 

오른쪽 그림을 예시를 들면

1 방문    2개 추가(2,3)

2 방문   2개 추가 (1,3)

3 방문  2개 추가(1,2)

총 간선의 개수는 6개이다. 이렇게 나온 이유는 같은 선을 중복해서 계산하기 때문이다. 중복해서 계산을 안 하려고 하면 구현이 어려워진다. 

구한 간선의 개수를 나누기 2 해주고 +1 를 해주고 노드의 개수와 같으면 트리이다.

6/2 +1  = 4  

4와 3(노드의 개수)는 다르므로 오른쪽 그림은 트리가 아니라 그래프이다. 

---

#풀이 코드      

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

public class Main {
    static List<List<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));
        int testCase = 1;

        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

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

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

            for (int i = 0; i < m; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                graph.get(a).add(b);
                graph.get(b).add(a);
            }

            int treeCount = 0;
            for (int i = 1; i <= n; i++) {
                if (!visited[i]) {
                    treeCount += isTree(i);
                }
            }

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

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

    private static int isTree(int root) {
        Queue<Integer> queue = new LinkedList<>();
        int nodeCount = 0;
        int edgeCount = 0;
        queue.offer(root);

        while (!queue.isEmpty()) {
            int current = queue.poll();
            if (visited[current]) continue;
            
            visited[current] = true;
            nodeCount++;

            for (int neighbor : graph.get(current)) {
                edgeCount++;  //방문은 안 하더라도 자식 노드들의 간선은 추가해준다.
                if (!visited[neighbor]) {  // 방문을 안 했다면 방문한다.
                    queue.offer(neighbor);
                }
            }
        }

        return (edgeCount / 2) + 1 == nodeCount ? 1 : 0;
    }
}