[JAVA]4803 트리, 분리 집합

 📚 문제  

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

4803번: 트리

 

🔍 아이디어  

사이클 생성 시에 그래프가 아니다.

1. BFS/ DFS로 탐색 

연결된 노드를 탐색한다, 만약 방문했던 노드를 재방문 시에는 사이클 이므로 트리 개수에서 제외한다(-1), 다른 경우는 탐색 시작 시점의 노드에서 (+1)

2. Union Find

정점이 들어오면 두 정점의 부모정정을 찾고 union한다. 만약 부모정점이 동일하면 사이클인 경우이다. 따라서  부모정점이 동일한 경우 사이클 boolean 배열에서 해당 노드를 cycle로 체크하였다.

private static void union(int a, int b) {
    a = findParent(a);
    b = findParent(b);

    if (a == b) cycle[a] = true; //사이클인 경우
    else if (a < b) parents[b] = a;
    else parents[a] = b;
}

 

해당 경우 트리의 경우에는 시작노드가 자기자신이고, 사이클이 아니라면 트리이므로 트리의 개수를 1 증가시킨다.

//그래프 탐색
//사이클
int cnt = 0;
for (int i = 0; i < n; i++) {
    if (parents[i] == i && !cycle[i]) { 
    //나의 부모가 나인지(그래프의 시작점만 센다), 그래프의 시작점이 사이클인 경우 제외
        cnt++;
    }
}

 

해당 사항까지 진행하면 75% 에러 틀렸습니다가 나온다.
이는 cycle 이 전파되지 않기 때문이다.

[출처] https://www.acmicpc.net/board/view/107169 반례 테케 4 4 2 3 3 4 4 2 1 2 0 0 => Case 1: No trees.

그래프가 생성된 이후에 자식 노드가 사이클인 정점인 추가되는 경우 부모노드도 사이클로 체크해 주어야 한다. 

따라서 다음과 같이 사이클 전파 부분을 추가하면 

if (cycle[b] || cycle[a]) { //사이클 전파
    cycle[a] = cycle[b] = true;
}

 

통과한다. 

 

다음처럼 사이클 전파를 자식이 사이클인 부모에만 진행해도 된다(시간은 더 걸린다)

private static void union(int a, int b) {
    a = findParent(a);
    b = findParent(b);

    if (a == b) cycle[a] = true; //사이클인 경우
    else if (a < b) {
        parents[b] = a;
        if (cycle[b]) cycle[a] = true;
    } else {
        parents[a] = b;
        if (cycle[a]) cycle[b] = true;
    }
}

 

📝 풀이

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

public class boj_4803_트리 {
    private static int[] parents;
    private static boolean[] cycle;


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


        for (int tc = 1; ; tc++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            if (n == 0 && m == 0) break; //종료조건

            parents = new int[n];
            cycle = new boolean[n];
            for (int i = 0; i < n; i++) {
                parents[i] = i;
            }


            //그래프 연결
            while (m-- > 0) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken()) - 1;
                int b = Integer.parseInt(st.nextToken()) - 1;

                union(a, b);
            }

            //그래프 탐색
            //사이클
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                if (parents[i] == i && !cycle[i]) { //나의 부모가 나인지(그래프의 시작점만 센다), 그래프의 시작점이 사이클에 해당하는지
                    cnt++;
                }
            }

            sb.append("Case ").append(tc).append(": ");
            if (cnt == 0) {
                sb.append("No trees.");
            } else if (cnt == 1) {
                sb.append("There is one tree.");
            } else {
                sb.append("A forest of ").append(cnt).append(" trees.");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }

    private static void union(int a, int b) {
        a = findParent(a);
        b = findParent(b);

        if (a == b) cycle[a] = true; //사이클인 경우
        else if (a < b) parents[b] = a;
        else parents[a] = b;

        if (cycle[b] || cycle[a]) { //사이클 전파
            cycle[a] = cycle[b] = true;
        }
    }

    private static int findParent(int a) {
        if (a == parents[a]) return a;
        return parents[a] = findParent(parents[a]);
    }
}