그래프 이론 - 2. 탑승구

문제

공항에는 G개의 탑승구가 있으며, 각각의 탑승구는 1번부터 G번까지 번호로 구분된다. 공항에는 P개의 비행기가 차례대로 도착할 예정이며, i번째 비행기를 1번부터 gi(1 <= gi <= G) 탑승구 중 하나에 영구적으로 도킹하려 한다. 이 때, 다른 비행기가 도킹하지 않은 탑승구에만 도킹이 가능하다. 또한 P개의 비행기를 순서대로 도킹하다가 만약에 어떠한 탑승구에도 도킹할 수 없는 비행기가 나오는 경우, 그 시점에서 공항의 운행을 중단한다. 공항의 관리자는 최대한 많은 비행기를 공항에 도킹하고자 한다. 비행기를 최대 몇 대 도킹할 수 있는지를 출력해라

입력조건

• 첫째 줄에는 탑승구의 수 G(1 <= G <= 100,000)가 주어진다.
• 둘째 줄에는 비행기의 수 P(1 <= P <= 100,000)가 주어진다.
• 다음 P개의 줄에는 각 비행기가 도킹할 수 있는 탑승구의 정보 g(1 <= g <= G)가 주어진다. 이는
  i번째 비행기가 1번부터 gi번째(1 <= gi <= G) 탑승구 중 하나에 도킹할 수 있다는 의미이다.

출력조건

• 첫째 줄에 도킹할 수 있는 비행기의 최대 개수를 출력해라.

입력예시
4
3
4
1
1

출력예시
2

구현코드

import java.util.*;

public class Main {

    // 탑승구의 개수와 비행기의 개수
    public static int g, p;
    public static int[] parent = new int[100001]; // 부모 테이블 초기화

    // 특정 원소가 속한 집합을 찾기
    public static int findParent(int x) {
        // 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
        if (x == parent[x]) return x;
        return parent[x] = findParent(parent[x]);
    }

    // 두 원소가 속한 집합을 합치기
    public static void unionParent(int a, int b) {
        a = findParent(a);
        b = findParent(b);
        if (a < b) parent[b] = a;
        else parent[a] = b;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        g = sc.nextInt();
        p = sc.nextInt();

        // 부모 테이블상에서, 부모를 자기 자신으로 초기화
        for (int i = 1; i <= g; i++) {
            parent[i] = i;
        }

        int result = 0;
        for (int i = 0; i < p; i++) {
            int x = sc.nextInt();
            int root = findParent(x); // 현재 비행기의 탑승구의 루트 확인
            if (root == 0) break; // 현재 루트가 0이라면, 종료
            unionParent(root, root - 1); // 그렇지 않다면 바로 왼쪽의 집합과 합치기
            result += 1;
        }

        System.out.println(result);
    }
}

코드해석

문제를 보면 탑승구를 찾아서 들어가는 문제이다. 만약 4 라는 값이 들어오면 1, 2, 3, 4 탑승구에 들어갈 수 있고 이전에 탑승구에 들어가있다면 그 탑승구에는 들어갈 수가 없는 것이다.
탑승구를 전부 찾아보고 구할 수 도있겠지만 완전탐색으로 풀게되면 시간 초과가 일어난다.
그렇기 때문에 값이 4가 들어온다면 이제 4값을 findParent 를 진행시킨다. 그 이유는 이미 값이 있는지 없는지 확인하는 것이다. 4의 findParent 가 4라면 4를 3 와 unionParent 를 해준다.
왜냐하면 4값을 이제 들어간 것인거 때문에 3과 union해서 3값의 findParent 값을 넣는건데 이미 3 번 탑승구에도 비행기가 도킹 했을 수있기 때문에 그 findParent 값과 해주는 것이다. 그리고 root 값이 0 이 된다면 break 해주면 된다.