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

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

 

유니온-파인드를 통해 분리 집합을 구성하고,

주어진 경로를 탐색하며 부모(== 분리 집합 대표자)가 바뀐 횟수를 구하는 문제다.

 

단, 첫 원소 (맨 처음 강의를 들으러 이동)는 세지 않는다.

 

---

간만에 푸는 문제 분류라 첫 ac에 빵꾸가 많았다. 이후 수정해서 700 -> 400ms로 줄였다.

 

1. find에서 좌표 압축

2. parent 최신화하고 탐색 -> find()로 탐색

3 priority 배열 제거

(문제에서 강의 순서가 존재한다. 유니온 대표자를 정하는 기준으로 사용했는데, 결과적으로 불필요했다.)

4. 간선(edge)안만들고 바로 union (심지어 양방향으로 만들어서 union 두 번씩 함)

5. path 배열 제거

 

이전 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

class Main {

  static int[] parent, prio, path;

  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; i++) {
      parent[i] = i;
    }

    List<Integer>[] edge = new ArrayList[N + 1];
    for (int i = 1; i <= N; i++) {
      edge[i] = new ArrayList<>();
    }

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

      edge[a].add(b);
      edge[b].add(a);
    }

    path = new int[N + 1];
    prio = new int[N + 1];
    st = new StringTokenizer(br.readLine());
    for (int i = 1; i <= N; i++) {
      path[i] = Integer.parseInt(st.nextToken());
      prio[path[i]] = i;
    }

    for (int i = 1; i <= N; i++) {
      for (int next : edge[i]) {
        union(i, next);
      }
    }

    for (int i = 1; i <= N; i++) {
      parent[i] = find(i);
    }

    int ans = 0;
    int prev = parent[path[1]];

    for (int i = 1; i <= N; i++) {
      int cur = parent[path[i]];

      if (cur != prev) {
        ans++;
        prev = cur;
      }
    }
    System.out.println(ans);
  }

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

    if (a == b) {
      return;
    }

    if (prio[a] < prio[b]) {
      parent[b] = a;
    } else {
      parent[a] = b;
    }
  }

  static int find(int x) {

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

    return find(parent[x]);
  }
}

 

최종 코드

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

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());
    int ans = 0;

    parent = new int[N + 1];
    for (int i = 1; i <= N; i++) {
      parent[i] = i;
    }

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

    st = new StringTokenizer(br.readLine());
    int prev = find(Integer.parseInt(st.nextToken()));

    for (int i = 1; i < N; i++) {
      int cur = find(Integer.parseInt(st.nextToken()));

      if (cur != prev) {
        ans++;
        prev = cur;
      }
    }
    System.out.println(ans);
  }

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

    if (a < b) {
      parent[b] = a;
    } else {
      parent[a] = b;
    }
  }

  static int find(int x) {

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

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