백준 10775번 공항 :: 마이구미

이 글은 백준 알고리즘 문제 10775번 "공항" 을 풀이한다.

문제 풀이는 유니온-파인드(union-find) 또는 디스조인트-셋(disjoint-set) 이라고 불리는 자료구조를 이용한다.

유니온-파인드 이해 - http://mygumi.tistory.com/246

문제 링크 - https://www.acmicpc.net/problem/10775

오늘은 신승원의 생일이다.

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 도킹된 게이트에는 다른 비행기가 도착할 수 없다.

이렇게 공항을 운영할 경우 간혹 비행기가 어떤 곳에도 도킹하지 못하는 사고가 발생한다. 이러한 사고가 일어나면 공항의 평판이 급속히 나빠져, 이후 어떤 비행기도 도착하지 않으려 할 것이다.

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

gi가 주어진다면, 되도록이면 gi에 도킹하고, 도킹할 수 없다면, gi-1에 도킹하는 식으로 할 수 있다.

도킹이 가능하다면, (도킹한 게이트 - 1) 와 union을 해준다.

위와 같은 형태는 다음과 같은 효과를 얻을 수 있다.

gi 게이트에 접근할 시, 어느 게이트가 도킹 가능한 지 union으로 인해 부모를 통해 확인 가능하다.

다음과 같은 예제가 주어졌을 경우, 그림을 통해 확인해보자.

4
6
2
2
3
3
4
4

다음과 같은 게이트 노드가 존재한다.

2번 게이트가 도킹되었다.

다음 도킹을 위해 (2 - 1) 게이트와 union 해준다.

1번 게이트가 도킹되었다.

다음 도킹을 위해 (1 - 0) 게이트와 union 해준다.

3번 게이트가 도킹되었다.

union 과정 중 find 함수로 인해, 1, 2, 3 게이트의 부모는 0을 바라보게 된다.

위처럼 도킹 여부를 나타낼 수 있다.

최종적으로는 find 호출시 0이 나오게 된다면, 도킹할 게이트가 없다는 의미가 된다.

유니온-파인드 자료구조를 정확히 이해하고 있어야 문제 풀이를 이해할 수 있다.

위 그림 또는 코드를 보아서는 쉽게 이해하기 힘들 것이다.

union과 find 함수를 정확히 이해하길 바란다.

Github - https://github.com/hotehrud/acmicpc/blob/master/algorithm/disjoint-set/10775.java

static int[] parent = new int[100001];
 
private void solve() {
    int g = sc.nextInt();
    int p = sc.nextInt();
    int ans = 0;
 
    for (int i = 1; i <= g; i++) {
        parent[i] = i;
    }
 
    for (int i = 1; i <= p; i++) {
        int gi = sc.nextInt();
 
        int docking = find(gi);
        if (docking != 0) {
            merge(docking, docking - 1);
            ++ans;
        } else {
            break;
        }
    }
    System.out.println(ans);
}
 
public static void merge(int u, int v) {
    u = find(u);
    v = find(v);
    parent[u] = v;
}
 
public static int find(int u) {
    if (u == parent[u]) {
        return u;
    }
    return parent[u] = find(parent[u]);
}