그래프 문제 - 탑승구

그래프 문제

탑승구

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

공항에는 P개의 비행기가 차례대로 도착할 예정이며 i번째 비행기를 1번부터 G번째 탑승구 중 하나에 영구적으로 도킹해야 합니다.

이때 다른 비행기가 도킹하지 않은 탑승구에만 도킹할 수 있습니다.

또한 P개의 비행기를 순서대로 도킹하다가 만약에 어떠한 탑승구에도 도킹할 수 없는 비행기가 나오는 경우 그 시점에서 공항의 운행을 중지합니다. 공

항의 관리자는 최대한 많은 비행기를 공항에 도킹하고자 합니다.

비행기를 최대 몇 대 도킹할 수 있는지 출력하는 프로그램을 작성하시오.

입력 조건

• 첫째 줄: 탑승구의 수 G
• 둘째 줄: 비행기의 수 P
• 셋째 줄: ~ : 각 비행기가 도킹할 수 있는 탑승구 정보

출력

도킹할 수 있는 비행기 최대 수 출력

입출력 예시

// 입력
4
3
4
1
1

// 출력
2

풀이

서로소 집합 알고리즘 사용

• 가능한 큰 번호의 탑승구에 도킹
• 도킹 = 합집합 연산
• 집합의 루트가 0일 경우 도킹 불가능

과정

출입구 4개, 비행기 6대

• 도킹할 수 있는 탑승구 정보: 2 2 3 3 4 4

1. 비행기 1 도킹: 1, 2번 출구에 도킹 가능
   • 2번 노드 루트 = 2, 1번 노드의 루트 = 1
   • 2번 출구에 도킹
   • 2번 노드와 1번노드 합집합 연산
   • 2번 노드의 루트 노드 = 1
2. 비행기 2 도킹: 1, 2 탑승구에 도킹 가능
   • 2번 노드 루트 = 1 → pass
   • 1번 노드의 루트 = 1 : 도킹 가능
   • 1번 출구에 도킹
   • 0번 노드와 1번 노드 합집합 연산
   • 1번 노드의 루트 노드 = 0
3. 비행기 3 도킹: 1, 2, 3번 출구에 도킹 가능
   • 3번 노드 루트 = 3, 2번 노드 루트 = 0, 1번 노드의 루트 = 0
   • 3번 출구에 도킹
   • 3번 노드와 2번노드 합집합 연산
   • 3번 노드의 루트 노드 = 0
4. 비행기 4 도킹
   • 3번 노드 루트 = 0, 2번 노드 루트 = 0, 1번 노드의 루트 = 0
   • 모든 노드의 루트가 0 → 도킹 불가능
   • 종료

코드

# 특정 원소가 속한 집합을 찾는다.
def find_parent(parent, x):
    #루트 노드가 아니면 루트 노드를 찾을 때까지 재귀 호출
    if parent[x] != x:
        return 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())
docking= list(int(input()) for _ in range(p))

parent = [0] * (g+1)

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

result = 0
for i in range(p):
    data = find_parent(parent, docking[i])
    if data == 0:
        break
    union_parent(parent, data, data-1)
    result += 1

print(result)