백준 10775번 공항 (Python)

문제 링크

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

10775번: 공항

---

Test Case

---

문제 풀이

union-find문제 인데 완벽하게 이해를 하고 풀지는 못했다.
내가 확실히 이해한 부분은 g_i를 입력받았을 때 최대한 도킹을 많이 하기 위해서는 해당 번호의 게이트로 도킹하는 것이 제일 최선의 방법이라는 점이다.
처음에 문제만 봐서는 union-find 문제인지 알기어렵지만 문제 조건을 보면 G, P의 범위가 매우크기 때문에 일일히 확인하면서 빡구현하면 O(n^2)의 시간 복잡도를 가지게 된다.
0번 노드를 추가해야되는 점도 생각하지못했던 부분이다.

---

Source Code

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

# 탑승구 g
# 비행기 p
g = int(input())
p = int(input())
data = []
for i in range(p):
    data.append(int(input()))

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

result = 0
for i in range(p):
    root = find_parent(parent, data[i])
    if root == 0 :
        break
    union_parent(parent,root, root-1)
    result += 1

print(result)