[Python - Data Structure, Union Find] 10775 공항

📌 문제

오늘은 신승원의 생일이다.

 

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

 

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

 

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

 

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

📌 입력

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.

 

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.

 

이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.

📌 출력

승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

📌 문제 풀이

👨‍🏫 접근

모든 비행기는 1~G 까지의 게이트에 도킹할 수 있다. 그렇기 때문에 1번 게이트는 와일드카드로 남겨두는 것이 좋다. k번 게이트를 접근하려고 하는데 불가능하다면 k - 1, k - 2, ..., 2, 1 순으로 도킹하기 때문에 1번 게이트까지 이미 도킹되어 있다면 더 이상 도킹이 불가능해진다.

 

그래서 모든 순회는 역순으로 해준다. 이때, k 부터 k - 5번까지 이미 도킹이 되어있는 상태이고 n번째 비행기가 k번 게이트에 도킹하려고 한다면 바로 k - 6번 게이트로 유도하는 것이 좋다. 그렇기 때문에 매번 게이트로 도킹시킬 때, k의 부모를 k - 1로 설정해두는 것이 시간 복잡도를 줄일 수 있는 방법이다.

 

이때 사용하는 알고리즘이 유니온 파인드 트리이다.

👨‍🏫 문제 풀이

📄 전체 코드

import sys
input = sys.stdin.readline


def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]


def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    parent[a] = b


g = int(input())
p = int(input())

gates = [i for i in range(g + 1)]
cnt = 0
for _ in range(p):
    k = int(input())
    dock = find_parent(gates, k)
    if dock != 0:
        union_parent(gates, dock, dock - 1)
    else:
        break
    cnt += 1

print(cnt)

📄 준비

import sys
input = sys.stdin.readline


def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]


def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    parent[a] = b


g = int(input())
p = int(input())

gates = [i for i in range(g + 1)]
cnt = 0

기본적인 연산 함수를 생성하고 게이트의 부모를 설정하기 위해 리스트를 설정한다. 이때 유니온 합치기 연산에서 a의 부모는 b로 설정해준다. 이렇게 설정한 이유는 x번 게이트에 도킹한다고 할 때, x-1번 게이트로 부모를 설정해야 하기 때문이다. 이때, x번 게이트 혹은 x-1번 게이트가 이미 도킹되어 있을 수 있으니까 부모연산을 마치고 합쳐준다.

📄 풀이

for _ in range(p):
    k = int(input())
    dock = find_parent(gates, k)
    if dock != 0:
        union_parent(gates, dock, dock - 1)
    else:
        break
    cnt += 1

print(cnt)

도킹할 게이트의 부모를 찾아주고 그 부모 이전 게이트와 합쳐준다. 이로서 k번 게이트가 이미 도킹된 상태라면, 그의 부모를 찾아서 빈 게이트를 찾아낼 수 있다.

📌 총평

조금 어려웠다.