백준 10775 공항 (union-find algorithm)

문제 : 10775번: 공항 (acmicpc.net)

10775번: 공항

 

접근과정

각 게이트마다 비행기 한대씩을 도킹할 수 있습니다.

그리고 만약 g 값이 4 라면, 1,2,3,4 4개의 게이트 중 하나에 도킹할 수 있다는 의미가 됩니다.

 

첫 번째 비행기의 g값이 2 이고 두 번째 비행기의 g 값이 1 이라면, 당연히 첫 번째 비행기는 2번 게이트에 도킹해야

한다는 것을 알 수 있으며, 

따라서 직관적으로 최대한 마지막 번호에 도킹하는 것이 좋다고 볼 수 있습니다.

 

처음에 생각한 것은 for문을 통해 뒤의 비행기들의 g값을 비교하는 것을 생각해봤는데, 비행기의 개수가 최대

100000개 이기 때문에 시간적으로 불가능했습니다.

 

그래서 검색 중 union-find 알고리즘을 사용해야 한다는 것을 알게 되었고 kks227님의 블로그에서 유니온 파인드

관련 글을 보고나서 풀게 되었습니다.

 

 

풀이과정

1. 처음에 자기 자신이 루트가 되게끔 초기화를 해줍니다.

 

2. 입력받은 g 값을 토대로 find 연산을 통해 g의 루트값을 찾습니다.

2-1. 루트값이 0이 아니라면 도킹할 수 있다는 뜻이며, union(n,n-1) 연산을 해줍니다.

2-2. 루트값이 0이라면 도킹할 수 없다는 뜻이며 종료해야합니다.

 

만약 예시대로 4,1,1 을 시도한다면,

1. 입력값 첫번째인 4번의 루트값은 4번이므로, 해당 번호에 도킹할 수 있습니다.

2. union(4,3)을 통해 4->3 이 연결되며 만약 다음번에 인풋으로 4가 들어온다면 3번에 도킹할 수 있음을 의미합니다.

3. 입력값 두번째인 1번의 루트값은 1번이므로,  해당 번호에 도킹할 수 있습니다.

4. union(1,0)을 통해 1->0 이 연결되며 만약 다음번에 인풋으로 1이 들어온다면 0번을 반환하며 더이상 도킹할 수 없음을 의미합니다.

5. 입력값 세번째인 1번의 루트값은 위에서 업데이트 된 대로 0이며, 더이상 도킹할 수 없으므로

최대 비행기 개수는 2가 됩니다.

 

#include <iostream>
#include <set>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int g,p;
// 각 노드마다 루트값을 저장
int gate[100001];
bool checked[100001];

int finding(int x) {
    if(x == gate[x]) return x;
    gate[x] = finding(gate[x]);
    return gate[x];
}

void unioning(int a, int b) {
    a = finding(a);
    b = finding(b);
    // 루트가 같다면 그냥 리턴
    if(a == b) return;
    // 아니라면 합침
    gate[a] = b;
}

int main()
{
    int gt;
    int cnt = 0;
    scanf("%d %d",&g,&p);

    // 처음엔 자기 자신이 부모 노드인 것으로 설정
    for(int i=0; i<=g; i++) gate[i] = i;

    for(int i=0; i<p; i++) {
        scanf("%d",&gt);

        int parent = finding(gt);
        // 도킹 가능한 게이트가 없음
        if(parent == 0)
            break;
        else {
            cnt++;
            unioning(parent, parent-1);
        }
    }
    printf("%d\n",cnt);
}