[Union-Find] BOJ 10775 공항

 

🎈 백준 10775 공항

www.acmicpc.net/problem/10775

10775번: 공항

 

❗ 문제의 핵심, 풀이 과정

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

• 공항에는 P개의 비행기가 순서대로 도착할 예정이며, i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다.

• 가장 많은 비행기를 공항에 도킹시켜야 한다.

=> 도킹하는 과정을 탑승구 간의 합집합 연산으로 생각한다. 각 탑승구를 서로다른 집합으로 초기화한다.

=> 새롭게 도킹이 되면, 왼쪽의 집합과 합친다. 집합의 루트가 0이면 더 이상 도킹이 불가능한 것으로 판단한다.

 

• 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

=> 집합의 루트가 0이면 비행기 수를 출력히고 종료한다.

 

✅ 전체 코드

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)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

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

parent = [0] * (g + 1)
for i in range(1, g + 1):
    parent[i] = i

result = 0
for _ in range(p):
    data = find_parent(parent, int(input()))
    if data == 0:
        break
    union_parent(parent, data, data - 1)
    result += 1

print(result)

 

 

* 이것이 코딩테스트다 with 파이썬 - 나동빈