[python] 백준 - 10775 (공항)

골드2 문제이며, 제한 시간은 1초이다.

문제

해결 과정

처음에 생각한 아이디어는 비행기가 들어올 때, 그 비행기의 게이트 번호에 넣으려고 하고, 이미 차있는 게이트이면 1씩 줄여서 빈 곳에 넣는 방식으로 구현했다.

발생한 문제

이런식으로 구현하게 되면 최악의 경우 시간 초과가 발생할 수 있다. 이중 반복문을 사용하게 되는데, 연산 횟수가 1억이 넘어가기 때문이다. 따라서 이 문제를 풀기 위해 Union - Find 알고리즘에 대해 공부하게 되었다.

Union - Find 알고리즘

Union - Find 알고리즘은 서로소 집합 알고리즘으로써 기본적인 사용법은 서로소인 집합이 몇 개 존재하는지 판단하는 알고리즘이다.

우선 기본적인 구현에 대해 알아보면

1. 부모 테이블을 자기 자신의 값으로 초기화해준다.
2. 같은 집합에 있는 원소를 Union연산을 해준다.

• Union연산은 만약 1과 3이 같은 집합에 있다면, 초기에 부모 테이블에도 1에는 1, 3에는 3이 있을 것이다. 여기서 더 큰 값을 작은 값으로 만들어 준다. 따라서 1의 부모 테이블은 그대로 1이고, 3의 부모 테이블 값도 1이 된다.

3. find() 함수를 통해 부모 테이블의 값과 본인의 값이 같을 때까지 재귀를 돌린 후 루트 노드를 리턴한다.

이 방법의 문제는 최악의 경우 find() 함수가 모든 노드를 확인하게 되어 시간 복잡도가 O(V)가 된다는 것이다. 노드 번호가 1 2 3 4 5 이고, 모든 노드가 다 연결되어 있다고 하면, 부모테이블이 1 1 2 3 4 이며 모든 노드를 탐색하게 된다. 따라서 사용할 방식은 경로 압축이다.

경로 압축

경로 압축은 사실 크게 다른 건 없고, find() 함수를 재귀적으로 호출할 때, 부모 테이블 값을 바로 갱신한다는 점이다. 이렇게 되면 1 2 3 4 5일 때 부모 테이블이 1 1 1 1 1로 바뀌게 되어서 시간복잡도를 줄일 수 있다.

Union - Find 알고리즘을 조금 변형해서 푼 풀이

def find_parent(gate, x):
  if gate[x] != x:
    gate[x] = find_parent(gate, gate[x])
  return gate[x]

g = int(input())
p = int(input())
#부모 테이블을 자기 자신으로 초기화
gate = [i for i in range(g + 1)]
answer = 0

for _ in range(p):
  plane = int(input())
  docking_gate = find_parent(gate, plane)
  
  #밑에있는 주석을 참고했을 때, x = 1이며 gate[x] = 1인 경우까지 사용했다면,
  #그 다음상황은 gate[x] = 0이 될 것이며 0은 존재하지 않으므로 더이상 도킹할 수 없다는 뜻
  #따라서 반복문을 탈출한다.
  if docking_gate == 0:
    break
    
  #union 부분
  #gate[docking_gate]를 이미 사용했으니 -1번째 게이트로 연결시킨다.
  #따라서 find_parent()로 넘어갔을 때 x는 3인데 gate[x]는 2이므로
  #재귀적으로 돌아가서 x = 2와 gate[x] = 2이므로 비어있다고 판단해서
  #2로 넣고, gate[docking_gate] = 1 이 될 것이다.
  gate[docking_gate] = gate[docking_gate - 1]
  answer += 1
print(answer)

코드를 보면 gate라는 리스트가 부모 테이블의 역할을 하고있으며, 자기 자신으로 초기화까지 되는 걸 알 수 있다.

그리고 find_parent(gate, x)에서 find연산을 수행하고 있으며, 재귀적으로 호출할 때 gate[x]에 바로바로 값을 넣어줌으로써 경로 압축을 하고있다.

그 후 비행기에 대한 게이트 정보가 입력되면 docking_gate라는 변수에 find_parent 함수에 대한 리턴 값을 담는다. 여기서 이 리턴 값은 비행기가 도킹할 수 있는 게이트 번호를 리턴한다.

이제 union 부분을 먼저 보면, docking_gate에 담겨있는 값은 이미 사용한 값이기 때문에 그 이전 게이트로 부모 테이블을 바꿔준다. 이렇게 되면 find_parent 함수를 호출할 때, gate[x] != x가 되므로 gate[x] == x가 될 때까지 탐색해서 docking_gate에 넣어줄 것이다.

여기서 docking_gate의 값이 0이라는 것은 gate[1] != 1이라는 뜻이므로 게이트 1번까지 다 찼다는 의미가 되어서 더 이상 도킹할 수 있는 공간이 없다는 뜻이 되므로 반복문을 탈출한다.

후기

우선 Union - Find 알고리즘을 처음 접해서 이해하는데 시간이 걸렸고, 이 글을 작성하면서 한 번 더 복습이 되었다. 게다가 이 문제는 그대로 사용하는 것이 아닌 조금 응용해서 사용하기 때문에 이 문제에 어떻게 적용한 것인지에 대한 이해하는 시간도 상당히 소요되었다. 나중에 다시 풀어봐도 좋은 문제인 것 같다.