[백준][C++] 10775번: 공항 <236>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

생각의 흐름

원래 나의 첫 풀이는 Greedy 방식으로 매우 직관적인 코드를 작성했었다.

그냥 맨 뒤부터 확인하면 되겠다 생각 하였다.

 

따라서 맨 처음 나의 코드는 다음과 같았다. (73%에서 시간 초과 나는 코드)

#include <bits/stdc++.h>
#include <iostream>

using namespace std;
#define MAX 100001

int G, P;
int cnt;
vector<int> air;
bool gate[MAX];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> G >> P;

    for (int i = 0; i < P; i++) {
        int num;
        cin >> num;
        air.push_back(num);
    }

    int len = air.size();
    for (int i = 0; i < len; i++) {
        int maxNum = air[i];

        bool isClosed = false;
        for (int j = maxNum; j >= 1; j--) {
            if (gate[j] == false) {
                gate[j] = true;
                cnt++;
                break;
            }

            if (j == 1) {
                isClosed = true;
            }
        }

        if (isClosed) {
            cout << cnt;
            exit(0);
        }
    }
    cout << cnt;

    return 0;
}

하지만 Gold2가 이렇게 간단할수는 없는것인가.... 시간 초과가 발생하였다.

73%에서 시간 초과가 발생하고 있는 상황이다.

 

뭐가 문제인지 잘 파악되지 않아서 질문글들을 살펴보던 중 다음글을 찾을 수 있었다.

 

https://www.acmicpc.net/board/view/66677

글 읽기 - 시간제한을 좀 줄여도 될 것 같네요

위 글에 의하면 단순 Greedy 풀이가 너무 쉬워서, 의도적으로 Union Find 를 사용하도록 하기 위해 제한시간을 더 타이트하게 줄인것 같다.

 

따라서 나는 다음으로 Union-Find를 적용하기로 생각했다.

핵심은 도킹시킬 때 g번의 루트와 g-1번의 루트를 합치는 것이다.

g번의 루트가 0이 아니라면 도킹할 수 있는 게이트가 적어도 한 개는 남았다는 뜻이므로 도킹시키고, 0이라면 즉시 종료한다.

 

맨 처음 모든 Gate는 자기 자신의 번호를 parent로 가지고 있는다, 다음과 같이 말이다.

하지만 2번 비행기가 2번에 도킹하고 나면, 다음으로 2번 Gate에 오는 비행기는 1번으로 가도록 해줘야 한다.

이러한 이유 때문에 Union(i, i-1)연산을 진행하는 것 이다.

 

나의 코드

#include <bits/stdc++.h>
#include <iostream>

using namespace std;
#define MAX 100001

int G, P;
int cnt;
int parent[MAX];

int find(int u) {
    if(parent[u] == u) {
        return u;
    }
    return parent[u] = find(parent[u]);
}

void join(int a, int b) {
    int pa = find(a);
    int pb = find(b);

    if(pa != pb) {
        parent[pa] = pb;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> G >> P;
    for(int i = 0; i < MAX; i++) {
        parent[i] = i;
    }

    while(P--) {
        int num;
        cin >> num;
        
        if(find(num) == 0) break;
        else{
            cnt++;
            join(find(num), find(num)-1);
        }
    }
    cout << cnt;

    return 0;
}