[백준] 공항, 탑승구

출처:: www.acmicpc.net/problem/10775

분류:: 서로소 집합 알고리즘 , union-find

 

1. 문제 이해 및 해결과정

- 도킹 = union연산  - 비행기가 순서대로 들어오면 차례대로 도킹을 수행해야하는데, 가능한 큰 번호의 탑승구로 도킹을 수행한다고 해보자 - 새롭게 비행기가 도킹 되면, 해당 집합을 바로 왼쪽 집합과 합친다. - 단, 집합의 루트가 0이면 더 이상 도킹이 불가능하다  ex) 입력2의 경우, 4는 탑승구의 개수, 6은 비행기의 수    1.  2 -> 첫번째 비행기는 1부터 2까지의 탑승구 중 하나에 도킹, 2번 노드를 확인하는데 2번 노드의 루트는 2이다. 그러므로, 1번과 union   2.  2 -> 두번째 비행기는 1부터 2까지의 탑승구 중 하나에 도킹할 수 있다. 2번 노드를 확인해보면 2번 노드의 루트는 1이다. 그러므로 1번노드와 0 번 노드 union   3. 3 -> 세번째 비행기는 1부터 3까지의 탑승구 중 하나에 도킹할 수 있다. 따라서 3번 노드를 확인해보면, 3번 노드의 루트는 3이다. 그러므로, 3번과 2번 union   4. 3 -> 네번째 비행기는 1부터 3까지의 탑승구 중 하나에 도킹할 수 있다. 하지만 3번 노드의 루트가 0이므로, 더 이상 도킹할 수 없음을 확인할 수 있다.

- 입력2)

4
6
2
2
3
3
4
4

 

2. 풀이방법

 1. union-find

#탑승구
#
import sys
sys.stdin = open("input.txt","r")
g=int(input())
p=int(input())
parent=[0]*(g+1)
result=0
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

for _ in range(p):
    root=find_parent(parent,int(input()))
    if root==0:
        #종료
        break
    union_parent(parent,root,root-1) #바로 왼쪽 집합과 합치기
    result+=1

print(result)

 

3. 오답원인

 

4. 알게된 점