[10775번] 공항

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Union Find :: http://www.crocus.co.kr/683

이 문제는 자신이 도킹 할 수 있는 가장 높은 수의 게이트부터 도킹하면 된다.

그리고 자신이 어느 게이트에도 도킹 할 수 없게 된다면 비행기가 도킹할수 없기때문에 그 뒤로 비행기는 모두 무시한 채 현재 값만 출력하고 종료하면 된다.

따라서 유니온 파인드를 쓰되 부모 지정 과정에서 자신이 4번 게이트에 도킹했다면 자신의 부모를 3번으로 지정하면 된다.

그렇게 하여 차례대로 게이트를 메워 나가는 방식이다.

결국 유니온 파인드 코드의 파인드만 있으면 되는 문제이다.

유니온은 필요가 없는 이유가 merge 자체를 해주지 않고 자신의 부모를 자신의 바로 전 수로 지정하면 되기 때문이다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

#include <cstdio>   using namespace std;   int parent[100001];   int find(int s) {     if (parent[s] == s)          return s;          return parent[s] = find(parent[s]); }   int main() {     int n, m;     scanf("%d %d", &n, &m);       for (int i = 1; i <= n; i++)         parent[i] = i;       int ans, tmp, val;       for (ans = 0; ans < m; ans++)     {         scanf("%d", &val);           tmp = find(val);                  // 루트가 0이면 도킹 완료         if(!tmp)              break;           // 가장 높은 게이트부터 도킹하니 바로 아래 수를 도킹 할 수 있도록 부모 설정         parent[tmp] = tmp - 1;     }       printf("%d", ans);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus