10775번

10775번 - 공항

union-find set을 다시 공부하려고 문제를 푸는데, 사실 어떤식으로 사용해야 할지 몰랐다..

일단 그리디적으로 갈 수 있는 가장 큰 게이트를 방문해야 한다는 사실은 알았다. 

하지만 아무리 생각해도, 시간초과가 발생하는 방법밖에는 몰라서, 고민하다가 다른 분들 코드를 참고했다.

획기적이었다. 나는 생각도 못함

나는 자꾸, 공항 게이트와 비행기 시간을 뭔가 집합으로 연결하려고 했다.

즉, 게이트마다 집합을 만들고 확인하는 작업을 거치다 보니 O(10000 * 10000) 이라는 시간초과가 발생했다.

그런데 게이트들만 연결하면서, find 함수를 쓰다보니까 너무나 쉬운 문제가 되버렸다.

일단 게이트마다 parent 를 자기 자신으로 초기화 시켜준다.

그리고 그리디적으로 알았던 방식과 같이, 방문할 수 있는 가장 큰 게이트를 방문하면,

그 게이트의 parent 값을 하나씩 줄여준다. 그때마다 정답을 하나씩 증가시켜주고,

게이트의 parent 값이 0이면, 더 이상 비행기가 올 수 없다는 뜻이기 때문에, 정답을 출력해주면 된다.!

<정답 코드>

#include<iostream>
 
using namespace std;
 
int parent[100001];
int find(int x)
{
    if (x == parent[x])
    {
        return x;
    }
    else
    {
        return parent[x] = find(parent[x]);
    }
}
int main()
{
    int x[100001];
    int g, p, ans = 0;
    scanf("%d%d", &g, &p);
    for (int i = 1; i <= g; i++)
    {
        parent[i] = i;
    }
    for (int i = 0; i < p; i++)
    {
        scanf("%d", &x[i]);
    }
    for(int i=0;i<p;i++)
    {
        int t;
        t = find(x[i]);
        if (t == 0)
        {
            break;
        }
        
        ans++;
        parent[t] = t - 1;
    }
 
    printf("%d\n", ans);
    return 0;
}