들어가기 앞서
이번 문제를 풀면서 Union-Find 알고리즘을 처음 익혔다. 다른 풀이를 보면 대부분 재귀함수로 푸는 경향이 있는데, 개인적으로 재귀함수를 굉장히 싫어하기 때문에 선호하는 방법으로 여러 번 풀었지만 전부 시간초과가 났다.
따라서 나의 알고리즘이 어떤 문제가 있었는지를 중심으로 본 문제를 정리하고자 한다.
문제
오늘은 신승원의 생일이다.
박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.
공항에는 $G$개의 게이트가 있으며 각각은 1에서 $G$까지의 번호를 가지고 있다.
공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 $i$번째 비행기를 1번부터 $g_i$ (1 ≤ $g_i$ ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.
신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?
Union-find 알고리즘
예시로 예시 2번을 차용하였다.
게이트는 총 4개가 존재하며, [2, 2, 3, 3, 4, 4]번 비행기가 차례대로 들어온다.
2번 비행기가 오면 우선 2번 게이트에 정차시킨다.
그리고 2번 게이트의 대안 게이트로 1번 게이트를 설정한다.
이제 다시 2번 비행기가 오면 2번 게이트에 정차시킨다.
그러나 2번 게이트는 이미 첫 번째 2번 비행기가 점유하고 있기에, 2번 게이트의 대안 게이트인 1번 게이트에 정차시킨다.
이제 1번 게이트도 점유되었기 때문에, 1번 게이트의 대안 게이트로 가상의 0번 게이트를 설정한다.
이제 3번 비행기가 온다.
3번 게이트는 비어있기 때문에 3번 게이트에 3번 비행기를 정차시킨다.
이제 네 번째 비행기로 3번 비행기가 온다.
3번 게이트는 점유되어 있기 때문에 3번 게이트의 대안 게이트인 2번 게이트에 정차시키고자 한다.
그러나 2번 게이트 역시 점유되어있기 때문에 계속해서 대안게이트에 정차시키고자 한다면 최종적으로 가상의 게이트인 0번 게이트에 정차하게 된다.
그러나 0번 게이트는 실제로 존재하지 않기 때문에 해당 비행기는 정차할 수 없게 되고, 알고리즘은 종료된다.
코드
import sys
input = sys.stdin.readline
# 입력 받기
num_gates = int(input())
num_airplanes = int(input())
airplanes = [int(input()) for _ in range(num_airplanes)]
# 변수 초기화
alters = list(range(num_gates+1)) # 대안 게이트
def find_root(airplane):
stack = [airplane]
while True:
parking_gate = alters[airplane]
if parking_gate == airplane:
break
else:
stack.append(parking_gate)
airplane = alters[parking_gate]
while stack:
temp = stack.pop()
alters[temp] = parking_gate
return parking_gate
def union(a,b):
# b is bigger
a_root = find_root(a)
b_root = find_root(b)
alters[a_root] = b_root
# 게이트 찾기
cnt = 0
for i in range(num_airplanes):
airplane = airplanes[i]
root = find_root(airplane)
if root == 0:
break
union(root, root-1)
#print(alters)
cnt += 1
print(cnt)find_root는 비행기의 최종적인 대안 게이트를 찾는 함수이다.
그리고 union 함수는 gate a를 최종적인 대안 게이트로 하는 게이트들의 집합과, gate b를 최종적인 대안 게이트로 하는 게이트들의 집합을 하나로 묶어주는 역할을 수행한다.
비고
비고에서는 Union find 알고리즘을 체화시킬 때까지 실패했던 세 가지 실패 사례를 소개하도록 한다.
실패 1
import sys
input = sys.stdin.readline
# 입력 받기
num_gates = int(input())
num_airplanes = int(input())
airplanes = [int(input()) for _ in range(num_airplanes)]
# 변수 초기화
parents = list(range(num_gates+1)) # 부모 노드
#gates = [[] for _ in range(num_gates+1)] # 해당 비행기가 어디에 주차했는지 확인 (for log)
# 대안 게이트 찾기
def find_alternative (airplane, parents):
alter_gate = parents[airplane] # 해당 게이트의 대안 게이트
while alter_gate != 0:
if parents[alter_gate] == alter_gate: # 해당 게이트에 주차할 수 있다면
break
else: # 주차할 수 없다면
alter_gate = parents[alter_gate] # alter gate 최신화
return alter_gate
idx = 0
while idx < num_airplanes: # 모든 비행기가 올 때까지
airplane = airplanes[idx] # 비행기가 왔다.
if parents[airplane] == airplane: #만약 제 자리에 주차할 수 있다면
#gates[airplane] = airplane
parents[airplane] -= 1 # 이전 자리로 부모를 업데이트
else: # 제 자리에 주차할 수 없다면
alter_gate = find_alternative(airplane, parents)
if alter_gate == 0: # 만약 대안게이트가 0이라면
break
else:
#gates[alter_gate] = airplane # 다른 게이트에 주차
parents[alter_gate] -= 1 # 이전 자리로 부모를 업데이트
idx += 1
print(idx)첫 번째 실패 코드는 어떤 비행기가 해당 비행기가 해당 위치에 주차할 수 없을 때, 즉, $n$번 비행기가 $n$번 게이트에 주차할 수 없을 때, $n-1, n-2, n-3 ...$을 계속 탐색하면서 주차할 수 있는 공간을 찾는다.
예를 들어, [1,2,3,3]번 비행기가 차례대로 들어온다고 가정하자.
- 1번 비행기가 1번 게이트에 정차하고 대안 게이트로 0번을 설정한다.
- 2번 비행기가 2번 게이트에 정차하고 대안 게이트로 1번을 설정한다.
- 3번 비행기가 3번 게이트에 정차하고 대안 게이트로 2번을 설정한다.
- 3번 비행기가 3번 게이트에 정차하고자 했지만, 불가능 하기에 대안 게이트인 2번 게이트에 가고자 한다. 그러나 2번 게이트 역시 불가능하기에 앞으로 계속 탐색하면서 0번 게이트에 정차한다.
실패 2
import sys
input = sys.stdin.readline
# 입력 받기
num_gates = int(input())
num_airplanes = int(input())
airplanes = [int(input()) for _ in range(num_airplanes)]
# 변수 초기화
parents = list(range(num_gates+1)) # 부모 노드
#gates = [[] for _ in range(num_gates+1)] # 해당 비행기가 어디에 주차했는지 확인 (for log)
# 대안 게이트 찾기
def find_alternative (airplane):
alter_gate = parents[airplane] # 해당 게이트의 대안 게이트
while alter_gate != 0:
if parents[alter_gate] == alter_gate: # 해당 게이트에 주차할 수 있다면
break
# 주차할 수 없다면
alter_gate = parents[alter_gate] # alter gate 최신화
return alter_gate
idx = 0
while idx < num_airplanes: # 모든 비행기가 올 때까지
airplane = airplanes[idx] # 비행기가 왔다.
if parents[airplane] == airplane: #만약 제 자리에 주차할 수 있다면
#gates[airplane] = airplane
parents[airplane] = parents[airplane-1] # 이전 자리로 부모를 업데이트
else: # 제 자리에 주차할 수 없다면
alter_gate = find_alternative(airplane)
if alter_gate == 0: # 만약 대안게이트가 0이라면
break
#gates[alter_gate] = airplane # 다른 게이트에 주차
parent = parents[alter_gate]
parents[alter_gate] = parents[parent-1] # 이전 자리로 부모를 업데이트
idx += 1
print(idx)두 번째 코드는 $n$번 비행기가 $n$번 게이트에 정차할 수 없을 때, $n-1, n-2, n-3...$번 게이트를 계속 탐색하는 것이 아니라, $n-1$번 게이트의 최종적인 대안 게이트만 탐색한다는 점에서 첫 번째 실패 사례보다 더 적은 시간이 든다.
예를 들어, [1,2,3,3]번 비행기가 차례대로 들어온다고 가정하자.
- 1번 비행기가 1번 게이트에 정차하고 0번 게이트를 대안으로 삼는다.
- 2번 비행기가 2번 게이트에 정차하고, 1번 게이트의 대안인 0번 게이트를 대안으로 삼는다.
- 3번 비행기가 3번 게이트에 정차하고, 2번 게이트의 대안인 0번 게이트를 대안으로 삼는다.
- 3번 비행기가 3번 게이트에 정차하고자 하지만, 게이트가 이미 점유되어 있기에 대안인 0번 게이트에 정차한다.
4번째 단계에서 3번 게이트의 대안을 찾는 과정이 "3 -> 2 -> 1 -> 0"에서 "3 -> 0"으로 단축되었다.
그러나 해당 코드는 비행기가 내림차순으로 들어온다면 1번 코드와 실행에 있어 차이가 없다는 단점이 있다.
예를 들어 [3,3,2,3]번 비행기가 차례대로 들어온다고 가정하자.
- 3번 비행기가 3번 게이트에 정차하고 2번 게이트를 대안으로 삼는다.
- 3번 비행기가 3번 게이트에 정차하고자 했지만 점유되어 있기에 대한인 2번 게이트에 정차하고 1번 게이트를 대안으로 삼는다.
- 2번 비행기가 2번 게이트에 정차하고자 했지만 점유되어 있기에 대안인 1번 게이트에 정차하고 0번 게이트를 대안으로 삼는다.
- 3번 비행기가 3번 게이트에 정차하고 싶지만 점유되어 있기에 대안인 2번 게이트, 1번 게이트, 0번 게이트를 순차적으로 탐색한다.
마지막 3번 비행기가 3번 게이트의 대안을 찾는 과정이 여전히 "3->2->1->0"인 것을 확인할 수 있다.
실패 3
import sys
input = sys.stdin.readline
# 입력 받기
num_gates = int(input())
num_airplanes = int(input())
airplanes = [int(input()) for _ in range(num_airplanes)]
# 변수 초기화
alters = list(range(num_gates+1)) # 대안 게이트
children = [-1] * (num_gates+1) # 해당 게이트를 대안으로 사용하는 게이트
# 게이트 찾기
for i in range(num_airplanes):
airplane = airplanes[i] # 비행기가 왔다.
if airplane != alters[airplane]: # 제 자리에 주차할 수 있을 때
airplane = alters[airplane]
if airplane == 0:
break
children[airplane-1] = airplane # 이전 게이트에 연결
root = alters[alters[airplane-1]] # 이전 게이트가 가리키는 게이트
# 기존 게이트의 자식들을 전부 업데이트
stack = [airplane]
while stack:
temp = stack.pop()
if children[temp] != -1:
stack.append(children[temp])
alters[temp] = root
print(i)매 번 비행기가 들어올 때마다 대안 경로를 하나씩 찾기보다는, 대안 경로를 업데이트하고 다음 비행기는 대안 경로를 한 번에 찾을 수 있도록 코드를 수정해보았다.
이전 실패 사례보다 더 빠르게 해결될 것을 기대했지만, 기대 외로 오히려 실패 1보다 더 오랜 시간이 걸렸다.
이는 최종 대안 게이트를 업데이트하는 과정이, 실패 1이나 실패 2처럼 최종 대안 게이트를 탐색하는 과정보다 더 오래 걸리기 때문이라고 생각한다.
개선안 1
import sys
input = sys.stdin.readline
# 입력 받기
num_gates = int(input())
num_airplanes = int(input())
airplanes = [int(input()) for _ in range(num_airplanes)]
# 변수 초기화
alters = list(range(num_gates+1)) # 대안 게이트
def find_root(airplane):
stack = [airplane]
while True:
parking_gate = alters[airplane]
if parking_gate == airplane:
break
else:
stack.append(parking_gate)
airplane = alters[parking_gate]
while stack:
temp = stack.pop()
alters[temp] = parking_gate
return parking_gate
def union(root):
# b is bigger
b_root = find_root(root-1)
alters[root] = b_root
# 게이트 찾기
cnt = 0
for i in range(num_airplanes):
airplane = airplanes[i]
root = find_root(airplane)
if root == 0:
break
union(root)
cnt += 1
print(cnt)성공 코드에서는 특정 비행기를 기준으로 최종 대안 게이트(root)를 구하고, 이를 바탕으로 union을 수행한다.
그러나 최종 대안 게이트의 결과값은 어차피 최종 대안 게이트가 나오기 때문에 union method에서 해당 게이트를 기준으로 find_root를 한 번 더 실행 할 필요가 없다.
따라서
def union(a,b):
# b is bigger
a_root = find_root(a)
b_root = find_root(b)
alters[a_root] = b_root를
def union(root):
# b is bigger
b_root = find_root(root-1)
alters[root] = b_root와 같이 수정해준다.
좀 더 효율적이게 된 걸 확인할 수 있다.
'알고리즘 > 백준' 카테고리의 다른 글
| [백준] 1005. ACM Craft (python) (0) | 2022.12.23 |
|---|---|
| [백준] 2162. 선분 그룹 (python) (2) | 2022.12.23 |
| [백준] 1766. 문제집 (Python) (0) | 2022.12.23 |
| [백준] 16724. 피리 부는 사나이 (python) (1) | 2022.12.23 |
| [백준] 2629. 양팔 저울 (python) (0) | 2022.12.23 |