[BOJ] 10775:공항

0. 문제

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

10775번: 공항

 

1. 문제분석

- 비행기의 도킹은 가능한 가장 큰 번호의 게이트로 하는 것이 가장 효율적이라는 점과, 각 비행기에 주어진 도킹 가능 최대 게이트 값이 다른 비행기라도, 앞선 비행기들이 하나씩 게이트를 차지함에 따라실제로 도킹할 수 있는 게이트의 최대 번호(루트 노드)는 같아질 수 있다(같은 집합에 속한다)는 점에서 union-find 함수를 이용한 disjoint set(분리 집합)을 구현해 문제를 풀어야 함을 알 수 있다.

- parent[i]: i번째 게이트(자식노드)까지 도킹 가능할 때, 실제로 도킹 가능한 게이트 중 번호가 가장 높은 게이트(루트노드).

 

2. 주의할 점

- 분리 집합이란 서로 교집합이 없는 집합을 가리킨다. 따라서 합집합(union)의 연산만이 의미가 있다.

- parent 배열에 초깃값으로 자기자신을 넣어주어야 한다. 

- find 함수를 구현해서 사용한다. union-find 중 find 함수만 구현해서 사용해도 충분하다. 하지만 사실상 parent[now] = now - 1;가 union 함수의 역할을 하기는 한다.

• find 함수는 재귀를 통해 주어진 자식 노드의 루트 노드, 즉 해당 집합을 대표할 수 있는 노드 값을 찾아내고 그 값을 parent 배열에 다시 저장해준다.

3. 소스코드(Java)

// boj 10775 공항
// disjoint set, union-find

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

public class boj_10775 {
    static int g, p, ans = 0;
    // parent[i] : i번째 게이트(자식노드)까지 도킹 가능할 때, 실제로 도킹 가능한 게이트 중 번호가 가장 높은 게이트(루트노드).
    static int[] parent;


    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        g = stoi(br.readLine());
        p = stoi(br.readLine());
        parent = new int [g + 1];
        for (int i = 1; i <= g; ++i) parent[i] = i;
        while (p-- > 0) {
            int now = stoi(br.readLine());
            // 실제로 도킹할 게이트(루트노드) 찾기
            now = find(now);
            if (now <= 0) break;    // 더이상 도킹할 곳이 없음
            ++ans;
            parent[now] = now - 1;
        }
        System.out.print(ans);
    }

    static int stoi(String s) {return Integer.parseInt(s);}
    static int find(int child) {
        if (child == parent[child]) return child;
        return parent[child] = find(parent[child]);
    }


}

 

 

4. 여담

- 입력이 한 줄 씩 들어오다 보니 StringTokenizer를 안쓰게 되었다. 이 글 쓰면서 발견했다.

- 입력이 남았는데 그냥 안 받아버려도 런타임 에러가 나지는 않더라.. 신기했음..

- "가장 큰 번호의 게이트부터 채우는 것이 가장 효율적"이라는 생각을 하는 것부터가 이 문제를 푸는 시작인 것 같다.