[백준] 공항 : Union-Find

문제

http://boj.kr/10775

개요

문제에서 눈에 띄는 문장은

$i$번째 비행기를 1번부터 $g\_i$(1 ≤ $g\_i$ ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려하고 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다는 것이다.

$i$번째 비행기 마다 $g\_i$값이 입력 되는데 입력값 이하 번호의 게이트에만 도킹을 할 수 있다는 것이다.

그리고 도킹 가능한 최대 비행기 수를 구해야 한다.

문제풀이

문제를 읽고 조금만 보고 있으면 $O(GP)$의 풀이가 떠오르긴 한다. 

최대로 도킹을 하려면 우선 주어진 $g\_i$에 바로 도킹할 수 있는지 판단하고 도킹이 가능하면 바로 도킹을 해준다.
만약 바로 도킹할 수 없는 경우에는 $g\_i-1$에 해당하는 게이트에 도킹을 해준다.

즉 이문제는 Greedy하게 게이트를 1씩 줄여가면서 해당 게이트에 비행기가 이미 도킹 되어 있는지 없는지를 확인하는 문제이다.

선형적으로 계산했을 때 최악의 경우 각 게이트 마다 모든 게이트를 확인하는 경우가 있으므로 시간복잡도는 $O(GP)$가 된다.
그러나 이렇게 풀면 당연히 TLE가 터진다. (범위가 매우 큼)

그래서 생각할 수 있는 다른 아이디어는
만약 $g\_i$를 입력 받았을 때 $g\_i$이하의 번호를 가진 게이트 중에서 도킹이 가능한 게이트를 그 즉시 알 수 있다면? 에서 출발한다.

즉시 알 수 있게 하진 못해도 최대한 압축해서 $g\_i$보다 작은 번호의 게이트에 비행기가 비어있다는 정보를 전달하려면 $g\_i$번 게이트에 비행기를 도킹하고 나서 그 다음 가능한 게이트를 갱신해줘야 한다는 아이디어를 떠올릴 수 있다. 

즉 초기에 자기 자신을 가리키고 있는 상태에서 다른 노드를 가리키는 상태로 변경하는 작업이 필요하다.

이는 Union-Find 알고리즘으로 해결 가능하다.

airport 배열의 i번째 인덱스는 i-1을 값으로 가진다. (airport[i]=i-1)
이는 $g\_i$를 입력받고 $g\_i$에 도킹이 불가능 할 때 $g\_i-1$의 게이트에 도킹을 시도한다 라고 이해하면 된다.

그 다음 풀이 순서는 다음과 같다.

1. 비행기를 바로 도킹할 수 있으면 도킹해준다.
2. 바로 도킹할 수 없는 상황에는 find() 함수를 통해 airport 배열을 확인하면서 도킹을 할 수 있는 게이트를 찾는다.
3. 이 때 도킹을 할 수 있는 게이트를 발견하면 그 즉시 find() 함수에 인자로 전달한 모든 게이트 인덱스의 값을 도킹 가능한 게이트 인덱스의 값으로 갱신한다.

예를 들어 airport = [-1,0,1,2,3,4] 에서 $g\_i=4$ 라고 하고 4번과 3번 게이트에 도킹이 불가능 하다면 2번 게이트에 도킹을 해주어야 하고 airport는 [-1,0,1,1,1,1]로 변경된다. 이렇게 해주면 다음번에 $g\_i$가 3이나 4가 입력되면 도킹 가능한 게이트로 바로 1번 게이트를 가리키게 되므로 훨씬 효율적으로 도킹 가능한 게이트를 찾을 수 있다.

코드

import sys
sys.setrecursionlimit(10**5)
In = lambda : sys.stdin.readline().rstrip()
MIS = lambda : map(int, In().split())

def find(x):
  if x<=0:
    return -1
  if not vist[x]:
    vist[x]=1
    return airport[x]
  airport[x] = find(airport[x])
  return airport[x]

G = int(In())
P = int(In())
airport = [i-1 for i in range(G+1)]
vist = [0]*(G+1)
ans=0
for p in range(P):
  g=int(In())
  fg=find(g)
  if fg==-1:
    print(ans)
    sys.exit(0)
    break
  ans+=1
print(ans)