[알고리즘] Union-Find (유니온 파인드)

Union-Find (유니온 파인드)란?

• 그래프 알고리즘으로 합집합 알고리즘이다
• 상호 배타적 집합(Disjoint-set)이라고도 한다.
  ※ Disjoint set: 서로 중복되지 않는 부분 집합들로 나눠진 원소들에대한 정보를 저장하고 조작하는 자료구조

Union-Find (유니온 파인드) 특징

• 집합을 구현하는 데는 배열, 리스트 등을 이용할 수 있으나 그 중 가장 효율적인 트리 구조를 이용하여 구현
• 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘

알고리즘 문제

백준 1976 여행가자

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.

도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다.

문제 분석

각 도시들 간의 연결 여부와 여행 계획이 주어지고, 출발지에서 목적지까지 여행 가능 여부를 판별한다.
여행 계획에 포함된 도시들이 같은 그래프에 속해있는지 구한다.

 

    for (int i = 0; i < N; i++)
        parent[i] = i;

각 그래프의 root 노드를 저장하는 parent 배열을 선언하고, 초기 값은 자기 자신을 저장한다.

    static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x > y)
            parent[x] = y;
        else
            parent[y] = x;
    }

연결되어 있는 두 노드를 union하여 같은 root를 공유하도록 최신화한다.
두 노드의 root 값 중 작은 값을 root로 저장한다.

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

재귀 함수를 통해 그래프의 root 노드를 찾아 parent 값을 최신화하고, argument와 parent 값이 같을 경우, 루트 노드에 도달하였기 때문에 재귀를 중단한다.

풀이 코드

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

class Main {

    static int N, M;
    static int[][] map;
    static int[] parent;
    static String[] input;

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

    static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x > y)
            parent[x] = y;
        else
            parent[y] = x;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        map = new int[N][N];
        parent = new int[N];

        for (int i = 0; i < N; i++)
            parent[i] = i;

        for (int i = 0; i < N; i++) {
            input = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(input[j]);
                if (map[i][j] == 1) {
                    union(i, j);
                }
            }
        }

        boolean isCycle = true;
        input = br.readLine().split(" ");
        for (int i = 0; i < M - 1; i++) {
            int a = Integer.parseInt(input[i]) - 1;
            int b = Integer.parseInt(input[i + 1]) - 1;

            if (parent[a] != parent[b]) {
                isCycle = false;
                break;
            }
        }

        System.out.println(isCycle ? "YES" : "NO");
        br.close();
    }

}