[Algorithm]Baekjoon 10775 :: 공항

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

10775번: 공항

 
using namespace std;
 
 
int g, p;
int parents[100001] = { 0 };
 
int getParent(int node)
{
    if (node == parents[node]) return node;
    return parents[node] = getParent(parents[node]);
}
 
void unionParent(int a, int b)
{
    a = getParent(a);
    b = getParent(b);
 
    if (a < b) parents[b] = a;
    else parents[a] = b;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> g >> p;
 
    for (int i = 1; i <= g; ++i)
    {
        parents[i] = i;
    }
 
    int answer = 0;
 
    for (int i = 1; i <= g; ++i)
    {
        int input;
        cin >> input;
 
        input = getParent(input);
        if (input == 0) break;
 
        unionParent(input, input - 1);
        ++answer;
    }
 
    cout << answer;
}

 

주어지는 g[i]값들에 대해서, 반드시 뒤에서부터 배치하는게 이득이다.

그렇기 때문에 뒤에서부터 배치하려면 해당게이트에 배치됐는지 검사하면서 앞으로 점점이동해야하는데, 그러면 시간제한에 걸릴 수밖에 없다.

 

이 부분을 표현하기위해 UnionFind를 접목한다.

예를들어 6번에 배치했다면, 다음에 또 6에 배치하려고 시도할 경우 5에 배치해야한다는걸 알려줘야 한다. 이걸 UnionFind로 표현할 수 있다. 그냥 union(6,5), 즉 union(input, input-1)을 해버리며 된다.

5에 배치해야하는데, 이전에 이미 5,5,5,5,5가 주어져서 1,2,3,4,5 게이트에 전부 배치되어있다면 결국 root인 0이 반환될 것이다. 0이반환됐다는것은 이미 1까지 전부 배치했다는 의미이니, 그대로 종료시키면 된다.

 

 

이런식으로 접근하는 문제는 처음이였는데, 좋은 문제인 것 같다.