문제설명

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

• 입력
  • 첫째 줄에는 탑승구의 수 G(1 <= G <= 100,000)가 주어진다.
  • 둘째 줄에는 비행기의 수 P(1 <= P <= 100,000)가 주어진다.
  • 다음 P개의 줄에는 각 비행기가 도킹할 수 있는 탑승구의 정보 g(1 <= g <= G)가 주어진다. 이는
    i번째 비행기가 1번부터 g_i번째(1 <= g_i <= G) 탑승구 중 하나에 도킹할 수 있다는 의미이다.
• 출력
  첫째 줄에 도킹할 수 있는 비행기의 최대 개수를 출력해라.

접근

다른 비행기가 도킹하지 않은 탑승구에만 도킹이 가능
i번째 비행기가 1번부터 g_i번째(1 <= g_i <= G) 탑승구 중 하나에 도킹할 수 있다
도킹했다는 정보를 표현해야함 > 특정 비행기가 G에 도킹할 경우 최대한 많은 비행기를 도킹할 수 있음 > 이미 G에 도킹된 비행기가 있을 경우 이전 탑승구를 차례대로 탐색해야함 > 이전 탑승구가 모두 도킹됐음을 알려주는 방법이 필요함 > 서로소 집합 자료구조를 통해 같은 루트를 가질때 더 이상 도킹 불가함을 표현할 수 있음 > 현재노드와 직전노드에 대해 합집합 연산을 수행함 > 1번 탑승구에 대한 직전노드가 필요함(예제2의 경우에서 알 수 있음) > 가상의 0번 노드 생성 > 현재노드의 루트가 0인 경우 탐색을 종료함

풀이

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

def union_parent(parent):
  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

for i in range(e):
  a, b = map(int, input9).split())
  union_parent(parent, a, b)

result = 0
# 핵심 아이디어 구현 코드 
# (현재노드의 루트노드가 0인 경우를 이전 모든 탑승구가 모두 찼음을 의미)
for _ in range(p):
  data = find_parent
  if data == 0:
    break
  union_parent(parent, data, data - 1)
  result += 1

print(result)

배운점

서로소 집합 자료구조 표현시 루트노드 표현이 어려운 경우 새로운 가상 노드를 통해 쉽게 표현할 수 있다.