[Problem Solving] BOJ 10775 : 공항

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

 

P대의 비행기가 순서대로 공항에 들어오게 되는데, i번째 비행기는 1번부터 G[i]번 게이트중 하나에 도킹하려고 할 때, 비행기가 어느 게이트에도 도킹할 수 없다면 이후 어떤 비행기도 공항에 도착할 수 없다. 이 때 공항에 도착할 수 있는 비행기의 최대 수를 구하는 문제이다.

 

이 문제는 Union-Find로 해결할 수 있다.

G = 4일 때 parent 배열은 다음과 같다.

parent = [0, 1, 2, 3, 4]

i번째 요소의 값은 비행기가 1번부터 i번의 게이트에 도킹하려고 할 때, 비행기가 도킹할 수 있는 게이트 번호의 최댓값이다. find 결과의 값이 0이 나온다면 비행기가 어느 게이트에도 도킹할 수 없는 것이다.

 

6대의 비행기가 공항에 올 예정이고 각 비행기가 도킹 하려는 범위는

1번 비행기: 1번 부터 2번

2번 비행기: 1번 부터 2번

3번 비행기: 1번 부터 3번

4번 비행기: 1번 부터 3번

5번 비행기: 1번 부터 4번

6번 비행기: 1번 부터 4번

이라고 하자.

 

parent = [0, 1, 2, 3, 4]

1번 비행기가 도착했을 때 도킹 가능한 게이트 = find(2) = 2 -> 2번에 도킹한다. -> 게이트 2번과 2-1=1번을 union한다.

-> parent = [0, 1, 1, 3, 4]

2번 비행기가 도착했을 때 도킹 가능한 게이트 = find(2) = 1 -> 1번에 도킹한다. -> 게이트 1번과 1-1=0번을 union한다.

-> parent = [0, 0, 0, 3, 4]

3번 비행기가 도착했을 때 도킹 가능한 게이트 = find(3) = 3 -> 3번에 도킹한다. -> 게이트 3번과 3-1=2번을 union한다.

-> parent = [0, 0, 0, 0, 4]

4번 비행기가 도착했을 때 도킹 가능한 게이트 = find(3) = 0 -> 도킹 불가능

 

union연산이 수행된 횟수를 출력한다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <algorithm>
#include <stack>
#include <set>
#include <cmath>
#include <climits>
#define endl '\n'
using namespace std;

int G, P, answer = 0;
vector<int> g;
vector<int> parent;

void input()
{
    cin >> G;
    cin >> P;
    g.resize(P);
    parent.resize(G + 1);
    for (int i = 0; i < P; i++)
    {
        cin >> g[i];
    }
    for (int i = 0; i <= G; i++)
    {
        parent[i] = i;
    }
}

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

void union_(int x, int y)
{
    int px = find_(x);
    int py = find_(y);
    if (px <= py)
    {
        parent[py] = px;
    }
    else
    {
        parent[px] = py;
    }
}

void solution()
{
    for (int i = 0; i < P; i++)
    {
        int gateNumber = find_(g[i]);
        if (gateNumber == 0)
        {
            return;
        }
        else
        {
            ++answer;
            union_(gateNumber, gateNumber - 1);
        }
    }
}

void output()
{
    cout << answer << endl;
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    input();
    solution();
    output();

    return 0;
}