[이코테] 그래프 알고리즘 - 탑승구

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

공항에는 G개의 탑승구가 있으며, 각각의 탑승구는 1번부터 G번까지 번호로 구분된다. 공항에는 P개의 비행기가 차례대로 도착할 예정이며, $i$번째 비행기를 1번부터 $g_i$(1 <= $g_i$ <= G) 탑승구 중 하나에 영구적으로 도킹하려 한다. 이 때, 다른 비행기가 도킹하지 않은 탑승구에만 도킹이 가능하다. 또한 P개의 비행기를 순서대로 도킹하다가 만약에 어떠한 탑승구에도 도킹할 수 없는 비행기가 나오는 경우, 그 시점에서 공항의 운행을 중단한다. 공항의 관리자는 최대한 많은 비행기를 공항에 도킹하고자 한다. 비행기를 최대 몇 대 도킹할 수 있는지를 출력해라

입력조건

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

출력조건

• 첫째 줄에 도킹할 수 있는 비행기의 최대 개수를 출력해라.

사고과정

• 비행기와 탑승구 정보로 어떻게 그래프 데이터로 만드는지 감도 오지 않았다. 그래서 '순서대로'라는 키워드를 보고 위상정렬인가 싶었지만 풀지 못했음..
• 풀이를 보니 서로소 집합 자료구조 알고리즘을 사용했는데, '탑승구' 를 하나의 집합으로 보았다.
• 가능한 큰 번호의 탑승구로 도킹을 수행했다고 가정(왜냐하면 탑승구 번호가 주어질 때, 최대한 큰 번호의 탑승구로 비행기를 보내는 것이 도킹할 수 있는 비행기 개수가 최대로 되기 때문!)하고 '도킹'이라는 과정을 하나의 union 연산으로 이해할 수 있다고 한다.
• 단, union 연산 시, 어떤 탑승구 번호로 연결해야 하는지는 풀이에서 임의대로 만들어 정보를 부여받은 탑승구 번호 기준으로 -1 만큼 작은 탑승구 즉, 왼쪽에 있는 탑승구 번호로 연결해야 하도록 Union 연산을 하는 것으로 가정했다.(이걸 어떻게 시험장에서 떠올리지..? OMG다 증말..)
• 그리고 항상 부모 테이블을 만들 때, 0번 루트 노드가 자동으로 생기는데, 해당 문제에서는 특정 탑승구 번호를 부여받았을 때, find 연산을 수행해서 0번 루트노드이면 더 이상 도킹할 수 없다는 것으로 룰을 만들었다..
• 많이 배워간다...

풀이(스스로 못푼 풀이)

import sys

g = int(input())
p = int(input())

# 탑승구를 하나의 집합으로 간주하고 서로소 집합 알고리즘 활용
parent = [0] * (g+1)
for i in range(1, g+1):
    parent[i] = i


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

count = 0
for _ in range(p):
    data = find_parent(parent, int(input()))
    # 만약 주어진 g_i값의 루트노드가 0이라면 더이상 탑승구에 들어갈 수 없고 운행 중지
    if data == 0:  # find_parent() 함수 넣으면 바로 첫번째 재귀함수 return이 반환되므로 재귀함수 == 0 조건은 안 됨!
        break
    # 루트노드가 0이 아니라면 주어진 주어진 탑승구 번호의 루트 노드와 루트 노드-1을 union연산
    union_parent(parent, data, data-1)
    count += 1

print(count)