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

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

24391번: 귀찮은 해강이

 

문제

해강이는 앙중대학교에 다닌다. 해강이는 이번 학기에 강의코드 1번부터 N번까지 N개의 강의를 듣고 있다.

모든 강의는 강의코드와 동일한 번호의 건물에서 진행된다. 예를 들어, 강의코드가 1인 강의는 1번 건물에서 진행되고, 강의코드가 N-1인 강의는 N-1번 건물에서 진행된다.

해강이는 밖에 나오는 것을 싫어해서, 강의 시간표 순서대로 모든 강의를 들으면서 한 건물에서 밖으로 나와서 다른 건물로 이동하는 횟수를 최소화하고 싶다. 앙중대학교에는 다행히도 서로 연결되어 있는 건물들이 있어, 이 건물끼리는 밖으로 나오지 않고 이동할 수 있다.

해강이의 강의 시간표가 주어질 때, 밖에 나오는 것을 싫어하는 해강이를 위해 최소 몇 번만 밖에 나오면 되는지 구해보자. 맨 처음 강의를 들으러 이동하는 횟수는 세지 않는다.

 

유형 : Union - Find

 

접근 방식

• 연결된 건물끼리의 이동 횟수는 0이다. -> 분리 집합을 통해 연결된 건물들을 1개로 관리할 수 있어야 한다.
• 연결이 입력될 때마다 Union - Find를 통해 건물을 연결한다.
• 마지막에 전체 노드의 개수만큼 find() 함수를 수행해줘야 하는데 그 이유는 다음과 같다.
  • 아래쪽에 연결이 완성되고 다시 위쪽의 입력이 주어진 경우 아래쪽 노드들의 부모가 초기화되지 않는다.

전체 코드

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

public class Main {

    static int n,m;

    static int[] root;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

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

        root = new int[n+1];
        for(int i = 1 ; i <= n ; i++){
            root[i] = i;
        }

        for(int i = 1 ; i <= m ; i++){
            st = new StringTokenizer(br.readLine()," ");

            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            if(find(v1) != find(v2)){
                union(v1,v2);
            }
        }
        
        for(int i = 1 ; i <= n ; i++){
            find(i);
        }

        int[] board = new int[n];
        st = new StringTokenizer(br.readLine()," ");

        for(int i = 0 ; i < n ; i++){
            board[i] = Integer.parseInt(st.nextToken());
        }

        int count = 0;
        for(int i = 1 ; i < n ; i++){
            if(root[board[i]] != root[board[i-1]])
                count++;
        }
        System.out.println(count);

        br.close();
    }
    static void print(){
        for(int i = 1 ; i <= n ; i++){
            System.out.print(root[i]+" ");
        }
        System.out.println();
    }
    static int find(int x){
        if(x == root[x])
            return root[x];

        return root[x] = find(root[x]);
    }

    static void union(int x,int y){
        x = find(x);
        y = find(y);

        if(x < y)
            root[y] = x;
        else
            root[x] = y;
    }
}