백준 10775 공항 - python

G=int(input())
P=int(input())
a=[i for i in range(G+1)]

def find(i):
    if a[i] == i:
        return i
    else:
        a[i] = find(a[i])
        return find(a[i])

def union(n, m):
    p = find(n)
    q = find(m)
    a[p] = q
    return


ans=0
for _ in range(P):
    g=int(input())
    parent_g = find(g)
    if parent_g == 0:
        break
    union(parent_g, parent_g - 1)
    ans+=1
print(ans)

union find를 배웠습니다.

부모 1 2 3 4
자식 1 2 3 4

여기서 1과 2가 연결되면 2의 부모를 1로 바꿔줌으로써 1과 2의 연결을 표현합니다.

부모 1 1 3 4
자식 1 2 3 4

위와 같이 됩니다. (일반적으로 더 작은 값 쪽으로 합칩니다.)

이후 2와 3이 연결되었다고 한다면

부모 1 1 2 4
자식 1 2 3 4

가 됩니다.

그런데 여기서 부모 노드만 보고 1과 3이 연결되어 있는지는 한 번에 알 수 없습니다. (1의 부모는 1인데 3의 부모는 2이기 때문에)

따라서 이를 재귀를 이용해 파악해 줍니다.

3의 부모인 2 -> 2의 부모인 1 -> 1의 부모인 1

이렇게 여러 집합을 합쳐서 어떤 원소가 속해있는 집합을 찾는 과정을 union find라고 합니다.