[백준] 10775번 공항 파이썬 코드

코드

# 유니온 파인드 이용

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

def union(a,b,lst):
  a = find(a,lst)
  b = find(b,lst)

import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline

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

def union(a,b,lst):
  a = find(a,lst)
  b = find(b,lst)
  if a < b:
    lst[b] = a
  else: lst[a] = b

airport = int(input())
gate = [i for i in range(airport+1)]
visited = [0]*(airport+1)
airplane = int(input())
cnt = 0
for _ in range(airplane):
  planenum = int(input())
  dok = find(planenum, gate)
  if dok == 0: break
  union(dok, dok-1, gate)
  # 가장 큰 값부터 차례차례 채워야하므로 뒤에 채워지면 앞을 연결해준다
  # 앞과 연결하면, 이를테면 4번이 채워진 상태에서는 3번으로 가게 된다.
  # 최대한 많이 채워야하기 때문에 나온 줄
  cnt += 1
print(cnt)