탑승구 그래프

공항에는 G개의 탑승구가 있으며, 각각의 탑승구는 1번부터 G번까지의 번호로 구분됩니다. 공항에는 P개의 비행기가 차례대로 도착할 예정이며, i번째 비행기를 1번부터 gi번째 탑승구 중 하나에 도킹을 해야 합니다. 이때 다른 비행기가 도킹하지 않는 탐승구에만 도킹 할 수 있습니다.

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

예시 4 (탑승구의 수) 3 (비행기의 수) 4 < 각 비행기가 도킹할 수 있는 탑승구의 정보 1 1

… 일단 코테를 시작할때 문제의 유형이 뭔지 정확하게 파악을 해야 겠습니다. 사실 보면서도 서로소 문제인 것을 잘 몰랐습니다.

전체 탑승구가 4개이니 노드가 4개 있다고 가정을 해봅시다.

비행기가 순서대로 들어오면 도킹을 수행해야하는데 가장 큰 번호의 탑승구로 도킹을 수행한다고 가정하겠습니다. 이때 우리는 도킹하는 과정을 탑승구 간 합집합 연산으로 이해할 수 있습니다. 새롭게 비행기가 도킹이 되면, 해당 집합을 바로 왼쪽에 있는 집합과 합칩니다. 단 집합의 루트가 0이면 더 이상 도킹이 불가능 한 것으로 판단합니다.

첫번째 비행기는 1부터 2까지의 탑승구 중 하나에 도킹 할 수 있습니다. 따라서 2번 노드를 확인하는데 현재 2번 노드의 루트는 2가 됩니다. 그러므로 2번 노드와 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
        
#탑승구의 개수 입력받기
g = int(input())
#비행기의 개수 입력받기
p = int(input())
parent = [0] * (g+1) #부모 테이블 초기화

#부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1,g+1):
    parent[i] = i

부모를 찾고 두 원소의 부모 노드를 합치고 기본적인 값을 입력을 일단 받았습니다.

result = 0
for _ in range(p):
    data = find_parent(parent, int(input())) #현재 비행기의 탑승구의 루트 확인
    if data == 0: #현재 루트가 0이라면 종료
        break
    union_parent(parent, data, data-1) #그렇지 않다면 바로 왼쪽의 집합과 합치기
    result += 1

print(result)

겨로가로 바로 넘어가겠습니다. 이제 p만큼(비행기의 개수만큼) 반복을 하는데

현재 비행기의 탑승구 루트를 확인하고 루트가 0이 아니라면 왼쪽의 집합과 합치고 이를 반복한다고 합니다.

… 뭔지 아직도 모르겠네요