백준 - 24391 귀찮은 해강이(Java)

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

24391번: 귀찮은 해강이

 

유니온-파인드(Union-Find) 문제입니다.

혹시 유니온 파인드를 잘 모르시는 분은 https://ksb-dev.tistory.com/114 에 정리된 것이 있으니 읽어보시기 바랍니다.

 

결국 문제에서 묻는 질문은 '건물들이 연결되어 있는가?'입니다.

유니온-파인드를 사용하면 연결 된 것은 하나의 집합으로 묶을 수 있습니다.

 

연결 건물 정보를 받아 유니온을 하고, 강의 시간표에 따라 파인드 연산을 하면 해결할 수 있습니다.

 

[구현 코드]

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

public class Main {
    private static int n, m;
    private static int[] parents;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(stz.nextToken());
        m = Integer.parseInt(stz.nextToken());

        parents = new int[n + 1];

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

        for (int i = 0; i < m; i++) {
            stz = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(stz.nextToken());
            int b = Integer.parseInt(stz.nextToken());

            union(a, b);
        }

        stz = new StringTokenizer(br.readLine(), " ");
        int[] route = new int[n];
        for (int i = 0; i < n; i++) {
            route[i] = Integer.parseInt(stz.nextToken());
        }

        int cnt = 0;
        for (int i = 0; i < n - 1; i++) {
            int a = route[i];
            int b = route[i + 1];

            int r1 = find(a);
            int r2 = find(b);

            if (r1 != r2) cnt++;
        }

        bw.write(String.valueOf(cnt));

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

    private static void union(int a, int b) {
        int r1 = find(a);
        int r2 = find(b);

        if (r1 == r2) return;

        if (r1 > r2) {
            parents[r1] = r2;
        } else {
            parents[r2] = r1;
        }
    }

    private static int find(int n) {
        if (parents[n] == n) {
            return n;
        }
        // 상위 노드가 아닌 최상위 노드를 저장해 시간 단축
        return parents[n] = find(parents[n]);
    }
}