Union Find(유니온파인드), 서로소 집합을 활용한 사이클 판별

이전에 유니온파인드에 대해 다룬 적이 있다. 유니온파인드는 서로소 집합을 만드는 알고리즘으로, 각기 다른 서로소를 가진 집합을 판별하고 합치는 기술이다.  자세한 내용은 아래의 링크를 참고하길 바란다.

Union Find 관련 포스팅

Union Find(유니온 파인드) - 연관 문제: 백준(1717번) 집합의 표현

유니온 파인드를 이용하면 무방향 그래프에서 사이클이 발생하는지 알 수 있다. 그 방법은 모든 노드에 대해서 자신과 간선으로 이어져 있는 노드들에 대해 Union을 수행하는 것이다. 만약 사이클이 존재한다면 어떤 시점에서 Union()을 하기위해 find를 할 때 같은 루트 노드를 가지는 두 개의 노드가 존재하게 될 것이다.

초기 노드들의 루트 노드는 자기 자신이다, 1, 2번 노드는 간선이 있기 때문에 union-find가 수행되며,1번 노드가 2번 노드의 루트가 된다. 1, 3번 노드도 역시 간선이 있기 때문에 union-find가 수행되며, 1번 노드가 3번 노드의 루트가 된다. 2, 3번 노드는 union-find에 의해서 루트 노드가 1번으로 변경될 것이다. 4번은 연결된 간선이 없기 때문에 union-find가 수행되지 않는다. 즉, 4번의 루트는 자기 자신이다.

이렇게 무방향 그래프의 사이클이 생긴 경우에는 4번이 2번 노드와 연결되어 있기 때문에 union-find가 수행된다. 4번의 root 노드는 3번, 3번의 root 노드는 1번이기 때문에 find의 결과로 1이 반환되고, 2의 root 노드는 1번이기 때문에 1이 반환된다. 즉 둘이 같은 root 노드 상에 존재하고 있기 때문에 사이클이 있다고 판단할 수 있다.

 

전체코드

import java.util.*;

public class Main {

    // 노드의 개수(V)와 간선(Union 연산)의 개수(E)
    // 노드의 개수는 최대 100,000개라고 가정
    public static int v, e;
    public static int[] parent = new int[100001]; // 부모 테이블 초기화하기

    // 특정 원소가 속한 집합을 찾기
    public static int findParent(int x) {
        // 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
        if (x == parent[x]) return x;
        return parent[x] = findParent(parent[x]);
    }

    // 두 원소가 속한 집합을 합치기
    public static void unionParent(int a, int b) {
        a = findParent(a);
        b = findParent(b);
        if (a < b) parent[b] = a;
        else parent[a] = b;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        v = sc.nextInt();
        e = sc.nextInt();

        // 부모 테이블상에서, 부모를 자기 자신으로 초기화
        for (int i = 1; i <= v; i++) {
            parent[i] = i;
        }

        boolean cycle = false; // 사이클 발생 여부

        for (int i = 0; i < e; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            // 사이클이 발생한 경우 종료
            if (findParent(a) == findParent(b)) {
                cycle = true;
                break;
            }
            // 사이클이 발생하지 않았다면 합집합(Union) 연산 수행
            else {
                unionParent(a, b);
            }
        }

        if (cycle) {
            System.out.println("사이클이 발생했습니다.");
        }
        else {
            System.out.println("사이클이 발생하지 않았습니다.");
        }
    }
}

코드는 이것이 취업을 위한 코딩 테스트다 with python- 저자 나동빈 책의 JAVA 코드를 참고했다.