[BOJ 백준] 10775번 : 공항 (C++)

[BOJ 백준] 10775번 : 공항 (C++)

목차

• 01. 개요
• 02. 접근 방식
• 03. 정답 코드
• 04. 마무리

---

01. 개요

출처

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

 

문제

 

입력

 

출력

 

예시

 

---

02. 접근 방식

요약

1. 각 게이트는 자기 요소의 값을 배열로 저장 (1번 게이트 = 1, 3번 게이트 = 3.. )

2. g번을 가진 비행기는 g게이트가 가지고 있는 값에 배치

3. 해당 비행기가 배치된 게이트와 바로 앞에 있는 게이트를 서로 묶습니다. 그로 인해서, 같은 그룹에 속하게 됩니다.

4. 새로운 비행기가 도착했을 때, 해당 게이트의 값이 0인 경우, 더 이상 배치를 진행할 수 없습니다. 

 

과정

해당 문제는 union-find 알고리즘을 사용하면 빠르게 해결할 수 있습니다.

 

먼저, 각 게이트에 비행기가 도착했을 때, 배치될 게이트의 위치에 대한 정보 배열을 선언하겠습니다.

1번 게이트부터 G번 게이트까지 존재하지만, 0번 게이트도 같이 선언합니다.

0번 게이트는 현재 다른 게이트에 이미 비행기가 배치되었다는 의미로 사용합니다.

 

선언된 게이트 정보 배열은 초기에 자기 요소의 값을 배열로 저장합니다.

즉, 0번 게이트 = 0, 1번 게이트 = 1,... n번 게이트 = n의 값을 가지게 됩니다.

 

x번 비행기가 도착하면, x번 게이트가 가지고 있는 값인 게이트로 이동해서 배치해야 합니다.

만약에, 3번 비행기가 도착했을 때, 3번 게이트의 값이 3이라면, 현재 게이트에 배치할 수 있습니다.

하지만, 3번 게이트의 값이 2라면, 3번 게이트가 아닌 2번 게이트에 배치해야 합니다.

 

만약에 위 상황과 이어져서 2번 게이트의 값이 1이라고 하면, 3번 비행기는 1번 게이트에 배치해야 합니다.

즉, n번 게이트의 값이 n일 때만, 주차를 할 수 있고, n번 게이트의 값이 n이 아니라면, 해당 값의 게이트로 이동해야 합니다.

 

특정 게이트에 비행기가 배치되면, 바로 앞에 있는 게이트와 그룹으로 묶습니다.

그래서, 0번으로 묶일 때까지 계속해서 비행기를 배치할 수 있습니다.

 

 

예시 2번을 통해서 더 자세히 알아보겠습니다.

 

먼저, 아래 사진은 초기 정보입니다.

 

비행기를 처음부터 하나씩 배치하겠습니다.

2번 비행기가 도착했을 때의 상황입니다.

 

2번 게이트의 값은 2였으므로 2번 게이트에 배치할 수 있습니다.

그래서, 2번 비행기 또는 2번 게이트로 들어오는 비행기는 1번 게이트로 이동하라고 값을 변경합니다.

 

다음 2의 값을 가진 비행기가 또 도착했습니다.

현재, 2번 게이트는 게이트 1에 배치할 수 있다고 알려주므로, 1번 게이트에 배치해야 합니다.

현재, 1번 게이트도 사용했으니, 1번 게이트의 앞인 0번 게이트와 묶어줍니다.

따라서, 0번부터 2번 게이트는 현재 하나의 그룹을 형성합니다.

0번 게이트는 현재 배치할 수 없다고 알려주는 게이트입니다.

그러므로, 1번 게이트나 2번 게이트에 비행기가 도착하면, 해당 비행기는 배치할 수 없습니다.

 

 

다음으로 3의 값을 가진 비행기가 도착했습니다.

현재, 3번 게이트의 값은 3이므로 해당 비행기는 3번 게이트에 배치할 수 있습니다.

3번 게이트는 배치가 되었으므로 앞의 그룹과 묶습니다.

따라서, 0번부터 3번 게이트까지 하나의 그룹을 형성합니다.

 

3의 값을 가진 비행기가 또 도착했습니다.

3번 게이트는 2번 게이트에 배치할 수 있다고 말합니다.

2번 게이트는 1번 게이트에 배치할 수 있다고 말합니다.

1번 게이트의 값은 0이므로 배치할 수 없다고 말합니다.

즉, 1~3번 게이트에 배치할 수 없으므로 해당 비행기부터는 배치를 할 수 없습니다.

 

그로 인해, 게이트에 배치할 수 있는 비행기는 총 3대입니다.

 

 

주의점

n번째 게이트의 값이 n이 아닐 때, 다른 게이트로 이동해서 검색을 해야 합니다.

이는 중복으로 검사할 필요가 없으므로 검색 결과에 대한 최적화 과정이 필요합니다.

 

따라서, 위 과정에서 진행한 예시 2번에서 3의 값을 가진 비행기가 2번째 도착했을 때는 아래 표처럼 초기화되어야 합니다.

 

---

03. 정답 코드

// 골드 2 - 10775번 : 공항
// 작성자 : free4760(jeonghoe22)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// {1} {2} {3} {4}
// -> 4의 부모를 3 가리키기
// {1} {2} {3,4}
// -> 1의 부모를 0 가리키기
// {1} {2} {3,4}
// 다시 부모가 0이면, 접근 불가능

vector<int> g_parents;

// 부모 찾기
int find_parent(const int idx)
{
    if(idx == g_parents[idx]) return idx;

    // 현재 최상단의 부모 찾기
    g_parents[idx] = find_parent(g_parents[idx]);
    return g_parents[idx];
}

// 앞에와 서로 합치기
void union_set(const int idx)
{
    int parent = find_parent(idx);

    g_parents[parent] = parent-1;
}

int main()
{
    // 입출력 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    // 게이트 수 G, 비행기 수 P
    int G, P;
    cin >> G >> P;

    // 부모 가리키는 노드 정보 초기화
    g_parents = vector<int>(G+1, 0);
    for(int i = 0; i < G+1; i++)
    {
        g_parents[i] = i;
    }

    bool b_continue = true;
    int result = 0, plane = 0;
    for(int i = 0; i < P; i++)
    {
        cin >> plane;

        // 0이 아닐 경우, 사용 가능한 게이트가 있음.
        if(find_parent(plane) != 0 && b_continue)
        {
            result++;
            union_set(plane);
        }
        // 0일 경우, 사용 가능한 게이트가 없음.
        else
        {
            b_continue = false;;
        }
    } 
    cout << result << "\n";
}

 

---

04. 마무리

union-find 알고리즘에 대한 응용문제였습니다. 문제 해결을 위한 아이디어가 매우 중요하다고 깨닫게 된 문제였습니다.

 

---

 

읽어주셔서 감사합니다.

틀린 내용 지적은 언제나 환영입니다!