[백준] 10775 공항, python

https://www.acmicpc.net/problem/10775

 

 

i 번째 게이트에 비행기가 들어가면 'i번째 게이트 이하의 게이트 중에서 열린 게이트의 최대 번호'를 prev배열에 저장하고, find함수를 통해  경로 압축을 하였다.

find함수는 현재게이트 이전의 열린 게이트의 번호를 추적해 나가면서 prev 값을 경신시켜 준다. 

 

 

유니온 파인드 알고리즘, python

유니온 파인드 알고리즘, python

 

 

유니온 파인드의 find함수와 동작 방식이 같다.

 

 

 

예제 2번의 경우 find함수가 갱신되는 과정이다.

 

초기상태는 모든 게이트는 자신의 번호를 prev로 저장한다. 비행기가 게이트에 들어가면 prev값은 1 감소시켜 준다.

prev값이 0번이라면 해당게이트 이전에 열려있는 게이트가 없다는 뜻이므로 종료한다.

 

 

 

 

 

2번 게이트에 비행기가 들어가므로 게이트 2번의 prev값을 1 감소시켜 준다.

 

 

 

 

 

 

2번 게이트에 비행기가 들어온다. 2번 게이트 이전 게이트 중에서 열린 게이트는 1번이었으므로  0으로 갱신해 준다.

 

 

 

 

 

 

3번 게이트에 비행기가 들어온다. 3번 게이트 이전 게이트는 2번 게이트이다. 여기서 2번 게이트의 이전게이트는 0번 게이트이다. 따라서 화살표를 계속 따라가 마지막 위치가 최종적으로 3번 게이트의 이전게이트가 된다.

 

경로압축을 통해 3번게이트의 이전게이트는 0번 게이트로 갱신해 준다.

 

 

 

 

 

 

 

find함수를 통해 이전 게이트 번호를 갱신해 주면서 비행기를 더 이상 넣을 수 없을 때까지 반복해 주면 된다.

게이트 번호	prev	설명
2	[1,1,3,4]	find함수를 통해 나온 2번게이트 이전 열린게이트 번호는 2이다. 2번게이트에 비행기를 넣고 prev[2]을 1 감소시킨다.
2	[1,0,3,4]	find함수를 통해 나온 2번게이트 이전 열린게이트 번호는 1이다. 1번게이트에 비행기를 넣는고 prev[2]를 1 감소시킨다.
3	[1,0,1,4]	find함수를 통해 나온 3번게이트 이전 열린게이트 번호는 3이다. 3번게이트에 비행기를 넣는고 prev[3]를 1 감소시킨다.
3	[1,0,1,4]	find함수를 통해 나온 3번게이트 이전 열린게이트 번호는 0이다. 더 이상 비행기를 넣을수 없으므로 종료된다.
4		종료
4		종료

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

G = int(input())
P = int(input())
arr = [int(input()) for _ in range(P)]

prev = [x for x in range(G+1)]
answer = 0

# 게이트 번호를 갱신하면서 탐색
def find(n):
    if prev[n] != n:
        prev[n] = find(prev[n])
    return prev[n]
    

for i in range(P):
    g = arr[i]
    gate = find(g)

    # 남은 게이트가 없다면 break
    if gate<=0:
        answer = i
        break
    prev[gate] -= 1
else:
    answer = P

print(answer)