[그래프이론] 탑승구

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 20분

1. 문제 설명

- 비행기는 도킹할 수 있는 탑승구가 정해져 있다. 하지만 탑승구에 도킹해있는 비행기가 있으면 다른 비행기는 도킹할 수 없다. 탑승구에 더 이상 도킹이 불가능할 때까지 비행기를 받고자 할 때, 최대로 받을 수 있는 비행기는 몇 대인가?

2. 접근 방식

- 서로소 집합 알고리즘을 활용해서 문제를 풀 수 있다.

- 0번째 집합(parent[0])까지 만든다. 집합을 주어진 순서대로 앞선 원소와 묶어가다가  0번째 집합에 묶이면 반복을 종료한다. 

3. 코드

def find_parent(parent, a):
    if parent[a] != a:
        parent[a] = find_parent(parent, parent[a])
    return parent[a]

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
        
        
parent = [0] * (a+1)

for i in range(1, a+1):
    parent[i] = i
    
result = 0
### 핵심코드, 게이트는 주어진 수 중 최대한 큰 수에 넣으면서 루트노드를 하나씩 내린다.
for gate in planes:
    data = find_parent(parent, gate)
    if data == 0:
        break
    else:
        union_parent(parent,data, data-1)
        result+=1
print(result)

4. 코멘트

- 어떤 것을 노드로 둬야 할까에 대해 고민을 좀 오래했었던 것 같다.

- 비용에 관계없이 순서대로 처리하는 문제였는데, 그걸 모르고 여러가지를 생각하다가 또 틀렸었던 것 같다. 

- 서로소집합은 서로소 집합을 구현하는데 어렵지는 않지만, 알고리즘을 이해하는데 어려운 것 같다. '집합을 어떻게 묶고, 이 묶은 것을 어떤 것으로 해석할 것인가' 등에 대한 다양한 경험이 있어야 한다. 약간 그래프 이론 문제를 풀다가 정답을 보게 되면, 바로 옆에 아는 사람이 있었는데 모르고 있었던 것 같은 느낌이 든다.