백준 4803. 트리 [Java]

문제 : 트리

유형 : 트리, 그래프 탐색, 분리 집합

---

문제 해석

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

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

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

해결 전략

• 트리의 정의를 이용하는 방법과 분리 집합을 이용하는 방법이 있다.

• 트리의 정의를 이용한다.

  • 트리는 정점이 n개, 간선이 n-1개 있다.
  • 양방향 연결 트리인 경우 간선은 2 * (n-1)개 이다.

• 그래프 안에서 연결된 정점들을 같은 집합으로 묶어주고 사이클 여부에 따라 트리와 그래프를 구분한다.
  • 분리 집합(Union-Find) 알고리즘을 이용해 그래프 안에서 부분집합을 만든다. 부분집합 상태는 트리 또는 그래프
  • 각 부분집합 중에 트리의 개수를 찾아서 세준다.

설계, 구현

• 트리의 정의를 이용한 경우
  • 서로 연결되어 있는 정점의 부분집합들은 트리 또는 그래프이다.
  • 모든 방문하지 않은 부분집합에서 임의의 한 점을 기준으로 BFS 탐색을 한다.
  • 부분집합을 탐색하면서 노드의 개수와 간선의 개수를 세준다.
    • 부분집합이 양방향 트리일 경우에는 (노드의 개수 - 1) * 2는 간선의 개수와 같다.
    • 이외의 경우는 트리가 아니다.

• 분리 집합(Union-Find) 을 이용한 경우

  • 서로 연결되어 있는 정점의 부분집합들을 Union : merge() 한다.

  • Union : merge()중에 두 정점의 부모가 같다면 사이클 이 생긴 것으로 트리가 아닌 그래프이다.

    • 사이클이 나타나는 조건 if(u == v) 에 맞춰 check[]에 트리가 아닌 그래프 (false)를 구분해 준다.

      사실 check[] 없이 parent[]만을 이용해 트리가 아님을 표현할 수 있다.
      직관적인 이해를 위해 check[]를 만들었다.
      check[]를 이용한 경우 → if(check[find(i)]) set.add(find(i));
parent[]만 이용한 경우 → if(find(i) > 0) set.add(find(i));

  • 주의할 점

    • Union : merge() 중에 사이클이 생기는 경우, 노드의 부모 배열을 0으로 바꿔야 한다.

      • 왜냐하면 나는 Union : merge() 할 때 2개의 노드 u, v가 있을 때 u가 3이고, v가 2이면 더 작은 숫자가 조상이 되도록 parent[u]를 2로 바꿨다.
        

      • 예를 들어 위와 같이 트리가 아닌 그래프가 있다. 그러면 parent[2], parent[3], parent[4]는 2로 초기화된다.
        

      • 그리고 위 그림과 같이 1번 노드가 추가된다면 1번 노드와 1번노드의 조상 또한 사이클임을 표시해야 하는데,
        우선 parent[2]보다 더 작은 노드인 parent[1]이 부모가 되므로 parent[2] = 1이 되고 parent[1] 을 0으로 바꿔야 한다. 왜냐하면 노드의 정점은 1번부터 시작하며, 나는 더 작은 노드가 조상 이 되도록 코드를 짰으므로 가장 작은 음이 아닌 정수는 0이 가장 작으므로 사이클의 부분집합 조상은 0 이어야 한다.

        • 여기서 parent[1]을 -1과 같이 음수로 표시할 경우에는 find() 과정에서 parent[-1]을 참조하므로 ArrayIndexOutOfBoundsException 에러가 발생한다.
        • 음수가 아닌 무한대의 값으로 나타내기 위해서는 merge() 중에 더 작은 노드가 조상 이 되도록 하는 코드를 더 큰 노드가 조상 이 되도록 코드를 바꿔주면 됀다.

---

트리의 정의를 이용한 코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_4803 {
    static ArrayList<ArrayList<Integer>> graph;
    static boolean[] visited;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {

        int testCase = 1;
        while(true) {
            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<>();
            for(int i = 0; i < n + 1; i++) {
                graph.add(new ArrayList<>());
            }
            for(int i = 0; i < m; i++ ){
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
                graph.get(u).add(v);
                graph.get(v).add(u);
            }

            visited = new boolean[n + 1];

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

            if(count == 0) {
                sb.append("Case " + testCase++ + ": No trees.");
            } else if(count == 1) {
                sb.append("Case " + testCase++ + ": There is one tree.");
            } else {
                sb.append("Case " + testCase++ + ": A forest of " + count + " trees.");
            }
            sb.append("\n");
        }
        bw.write(sb.toString());
        bw.close();
        br.close();
    }

    static boolean bfs(int start) {
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(start);
        visited[start] = true;
        int node = 0, edge = 0;

        while(!q.isEmpty()) {
            int cur = q.poll();
            node += 1;
            visited[cur] = true;

            for(int next : graph.get(cur)) {
                edge += 1;
                if(!visited[next]) {
                    q.add(next);
                }
            }
        }

        return 2*(node-1) == edge ? true : false;
    }
}

---

분리 집합(Union-Find)을 이용한 코드

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

public class BOJ_4803_UnionFind {
    static int[] parent;
    static boolean[] check;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
    
    public static void main(String[] args) throws IOException {

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

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

            parent = new int[n + 1];
            check = new boolean[n + 1];

            for(int i = 1; i < n + 1; i++) {
                parent[i] = i;
                check[i] = true;
            }

            for(int i = 0; i < m; i++ ){
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
                merge(u, v);
            }

            HashSet<Integer> set = new HashSet<Integer>();
            for(int i = 1; i < n + 1; i++) {
                if(check[find(parent[i])]) set.add(find(parent[i]));
            }

            int count = set.size();
            if(count == 0) {
                sb.append("Case " + testCase + ": No trees.");
            } else if(count == 1) {
                sb.append("Case " + testCase + ": There is one tree.");
            } else {
                sb.append("Case " + testCase + ": A forest of " + count + " trees.");
            }
            testCase++;
            sb.append("\n");
        }

        bw.write(sb.toString());
        bw.close();
        br.close();
    }

    static int find(int x) {
        if(x == parent[x]) return x;
        else return parent[x] = find(parent[x]);
    }

    static void merge(int u, int v) {
        u = find(u);
        v = find(v);

        if(u == v) check[u] = false;

        if(u > v) parent[u] = v;
        else parent[v] = u;
    }
}