[CCC] 탑승구

문제

 공항에는 G개의 탑승구가 있으며, 각각의 탑승구는 1번부터 G번까지의 번호로 구분됩니다.

 

공항에는 P개의 비행기가 차례대로 도착할 예정이며, i번쨰 비행기를 1번부터 $g_{i}$번째(1 $\le$ $g_{i}$ $\le$ G)

탑승구 중 하나에 영구적으로 도킹해야 합니다. 이때, 다른 비행기가 도킹하지 않은 탑승구에만 도킹할 수 있습니다.

 

 또한 P개의 비행기를 순서대로 도킹하다가 만약에 어떠한 탑승구에도 도킹할 수 없는 비행기가 나오는 경우, 그 시점에서 공항의 운행을 중지합니다. 공항의 관리자는 최대한 많은 비행기를 공항에 도킹하고자 합니다. 비행기를 최대 몇 대 도킹할 수 있는지를 출력하는 프로그램을 작성하세요.

 

입력 조건

- 첫째 줄에는 탑승구의 수 G(1 $\le$ G $\le$ 100,000)가 주어집니다.

- 둘째 줄에는 비행기의 수 P(1 $\le$ P $\le$ 100,000)가 주어집니다.

- 다음 P개의 줄에는 각 비행기가 도킹할 수 있는 탑승구의 정보 $g_{i}$(1 $\le$ $g_{i}$ $\le$ G)가 주어집니다. 이는 i번째 비행기가 1번부터 $g_{i}$번쨰 (1 $\le$ $g_{i}$ $\le$ G) 탑승구 중 하나에 도킹할 수 있다는 의미입니다.

 

출력 조건

- 첫째 줄에 도킹할 수 있는 비행기의 최대 개수를 출력합니다.

 

입력 예시1

4
3
4
1
1

 

출력 예시1

2

---

 처음에 위상정렬 문제인 줄 알았는데, 알고보니 서로소 집합 알고리즘을 이용하면 간단하게 풀 수 있는 문제였습니다.

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

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

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

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

 핵심은 $g_{i}$이하의 탑승구에만 도킹할 수 있다는 것입니다. 이때 도킹이 가능한가, 가능하지 않은가를 판별하는 기준으로 왼쪽 노드의 루트노드를 사용할 수 있습니다. 즉, 입력으로 받는 $g_{i}$들에 대해서 왼쪽 노드를 합치는 연산을 진행하면 이미 도킹된 노드들이 점차 같은 집합으로 묶이게 됩니다.

 

 만약 왼쪽 노드의 값이 0이라면, 이는 실제 존재하는 도킹 위치가 아니므로 순회를 종료합니다. 정답은 Union연산이 발생한 횟수, 즉 도킹이 발생한 횟수이므로 cnt변수를 정답으로 리턴합니다.