[ 10775 ] [ Union-find] 공항

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

10775번: 공항

 

---

풀이 과정

---

1. Union-find 알고리즘을 응용하는 문제이다.
   • find(i)가 의미하는게 게이트 번호가 i일 때 넣을 게이트의 다음 위치라고 보면 된다.
2. 입력받은 게이트의 부모 노드를 찾고(find), 부모노드와 부모노드 - 1 노드를 union 해준다.
   • 부모 노드에는 비행기를 넣었으므로 다음 위치는 (부모노드-1)의 부모노드이기 때문이다.
   • 이 때, Union 연산을 할 때, i 이하의 게이트를 찾아야 하므로 두 점 중에서 큰 번호의 부모를 수정해야 한다.
3. 부모 노드를 찾았을 때, 부모 노드가 0이라면 어느 게이트에도 도킹할 수 없는 것이므로 루프를 중지한다.
4. 결괏값을 출력시켜 준다.

---

소스 코드

---

 

import sys

input = sys.stdin.readline

sys.setrecursionlimit(10**5)

def find(parent, a):
    if parent[a] != a:
        parent[a] = find(parent, parent[a])
    return parent[a]

def union(parent, a, b):
    p1 = find(parent, a)
    p2 = find(parent, b)
    if p1 < p2:
        parent[p2] = p1
    else:
        parent[p1] = p2

G = int(input().rstrip())
P = int(input().rstrip())
parent = [i for i in range(G+1)]
answer = 0

for i in range(P):
    ap = int(input().rstrip())
    where = find(parent, ap)
    if where == 0:
        break
    union(parent, where, where-1)
    answer += 1

print(answer)