[백준] 24391: 귀찮은 해강이 - JAVA

15 Feb 2024 in Algorithm on 자료 구조

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

풀이

건물을 돌아다닐 때, 서로 연결되어있는 건물은 밖으로 안나가고 이동할 수 있다.

몇 번 밖으로 나와야하는지 구해야한다.

서로 연결된 건물들을 union메서드를 이용해 한 parent로 묶었다.

그렇게해서 i번 건물과 i-1번 건물이 parent가 다르다면 answer을 1증가시켰다.

---

메모리: 52100KB

시간: 456ms

언어: Java 11

코드

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

public class Main {
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        parent = new int[n + 1];
        for (int i = 1; i < n + 1; i++) {
            parent[i] = i;
        }

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

        int answer = 0;
        int[] lecture = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            lecture[i] = Integer.parseInt(st.nextToken());
            if (i > 0 && find(lecture[i]) != find(lecture[i - 1])) {
                answer++;
            }
        }

        System.out.println(answer);
    }

    private static void union(int a, int b) {
        int pa = find(a);
        int pb = find(b);

        if (pa > pb) {
            parent[pb] = pa;
        } else {
            parent[pa] = pb;
        }
    }

    private static int find(int a) {
        if (parent[a] == a) {
            return a;
        } else {
            parent[a] = find(parent[a]);
            return parent[a];
        }
    }

}