백준 10775번 공항

문제 링크입니다: https://www.acmicpc.net/problem/10775

Union Find(=Disjoint Set) 자료구조를 사용하는 알고리즘 문제였는데 기존에 풀었던 문제들보다 난이도가 있는 문제였습니다.

저도 kks227(https://kks227.blog.me/220791837179?Redirect=Log&from=postView)님의 포스팅을 보고나서야 풀 수 있었습니다.

문제에서 요구하는 바는 최대한 많은 비행기를 배치하되 게이트 당 하나의 비행기를 배치하는 것이였습니다.

상당히 간단해보이지만 매 쿼리마다 모든 게이트를 확인한다면 TLE가 발생하는 것이 자명하기 때문에 구현이 어려운 문제였습니다.

kks227님의 알고리즘은 아래와 같습니다.

1. 모든 비행기가 게이트(1~G) 중 한 군데에 위치할 수 있기 때문에 G번, G-1번, G-2번, ..., 1번 순으로 게이트가 있는지 확인해보는 것이 핵심 아이디어였습니다.

2. G번 게이트에 비행기가 배치되면 merge(G-1, G)를 호출해 G-1번 게이트의 루트가 G번이 되게 하고 G-1번 게이트에 비행기가 배치되면 merge(G-2, G-1)을 호출해 G-2번 게이트의 루트가 G-1번이 되게 하고 ... 1번 게이트가 차면 merge(0, 1)을 호출하여 0번 게이트(존재하지 않은 게이트)의 루트가 1번 게이트가 되게 합니다.

3. 따라서 1번 게이트까지 찼다면 findParent 함수를 호출했을 때 무조건 1 보다 작은 수가 호출 되기 때문에 모든 게이트가 꽉 찼다는 것을 알 수 있습니다.

#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;

 

const int MAX = 100000 + 1;

 

int G, P;

int arr[MAX];

 

//루트를 찾는 함수

int findParent(int num)

{

        if (arr[num] < 0)

                 return num;

 

        int parent = findParent(arr[num]);

        arr[num] = parent;

        return parent;

}

 

void merge(int aParent, int bParent)

{

        //집합의 크기가 더 큰 쪽으로 합쳐진다

        if (abs(aParent) >= abs(bParent))

        {

                 arr[aParent] += arr[bParent];

                 arr[bParent] = aParent;

        }

        else

        {

                 arr[bParent] += arr[aParent];

                 arr[aParent] = bParent;

        }

}

 

//집합의 크기를 계산하지 않고 합친다

void changeRoot(int prevGate, int curGate)

{

        prevGate = findParent(prevGate);

        curGate = findParent(curGate);

 

        arr[curGate] = prevGate;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        cin >> G >> P;

 

        memset(arr, -1, sizeof(arr));

 

        int result = 0;

        bool dock = true;

        for (int i = 0; i < P; i++)

        {

                 int temp;

                 cin >> temp;

 

                 if (!dock)

                         continue;

 

                 int openGate = findParent(temp);

                 //root가 1 이상이라면 게이트가 하나 이상 비어있다

                 if (openGate > 0)

                 {

                         result++;

                         changeRoot(openGate - 1, openGate);

                 }

                 //더 이상 빈 게이트가 없을 경우

                 else

                         dock = false;

        }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~