Union-Find 알고리즘 이용하기!!!
처음 생각한 풀이 (오답,,)
이 문제는 여러 그래프 집합으로 나뉘지 않고
이미 사용한 게이트 vs 사용 가능한 게이트 이 둘로만 나뉜다.
-> 그럼 이미 사용한 게이트 = -1, 사용 가능한 게이트 = 자기자신
으로 설정하기
1. parent[i] == i 이면 parent[i] = -1로 바꿔주기
2. parent[i] != i 이면 parent[j] != -1 (j==i보다 작은 수들의 집합) 인 j중 최댓값
바뀐 풀이
Union-Find 알고리즘이라고 생각하면 복잡했는데 다른 방식으로 생각하니까 더 이해하기 쉬웠다.
예제2) 로 이해하기
2 -> 2 -> 3 -> 3 -> 4 -> 4 순서대로 비행기가 게이트에 들어옴| 노드번호 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 부모 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
원래는 자기 자신만 가리키다가
find(2) -> gates[2] = 1
2번 게이트에 비행기가 들어왔을때
그럼 gates[2] = (다음에 들어갈 수 있는 게이트의 번호) 를 넣어주기
- 여기서 (다음에 들어갈 수 있는 게이트의 번호)을 구하는 방법은 find 함수를 사용하여 부모들 중에
gates[i]=i(자기자신)을 갖는 i를 찾는거임
| 노드번호 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 부모 노드 번호 | 1 | 1 | 3 | 4 | 5 | 6 |
find(2) -> gates[2] = find(gates[2]) = find(1) = 1
| 노드번호 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 부모 노드 번호 | 0 | 1 | 3 | 4 | 5 | 6 |
find(3) -> gates[3] = 2
| 노드번호 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 부모 노드 번호 | 0 | 1 | 2 | 4 | 5 | 6 |
find(3) -> gates[3] = find(gates[3]) = find(2) = find(1) = 0
| 노드번호 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 부모 노드 번호 | 0 | 1 | 2 | 4 | 5 | 6 |
find(3)==0 -> 종료
주의
파이썬은 재귀에 취약하다,, 백준에서는 재귀가 1000번에 근접하게 발생하면 런타임에러 RecursionError가 발생한다.
import sys
sys.setrecursionlimit(10**6)위의 코드를 통해 재귀 가능 횟수를 늘릴 수 있다.
정답코드
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
gate = int(input())
plane = int(input())
gates = [i for i in range(gate+1)] # 처음 게이트는 자기 자신만 가리키도록 설정
arr = [int(input()) for _ in range(plane)] # 비행기 들어오는 순서대로 배열에 넣기
cnt = 0
def find(i):
if gates[i] == i:
gates[i] = i-1
return i
gates[i] = find(gates[i])
return gates[i]
for i in arr:
if find(i) == 0:
break
cnt += 1
print(cnt)후기
이 문제를 통해 Union-Find 라는 알고리즘을 처음 알게 되었다. 솔직히 공부를 하고 풀긴 했지만 "Union-Find를 완전히 이해했다.", "Union-Find를 올바르게 사용하여 코드를 작성했다."는 말은 절대 못할거 같다.
나중에 분리 집합을 언제 사용해야 유리한지, 어떻게 사용하는 것이 효과적인지 다시 공부하자!!
