✔️ gold 2
그래프 이론
그래프 탐색
너비 우선 탐색
문제 흐름
구현 자체는 생각보다 단순하게 시작했다.
최단거리를 찾는 문제이기 떄문에 BFS를 선택했고,
그냥 같은 하이퍼튜브에 포함된 노드(역)을 모두 엣지로 이어주었다.
생각보다 쉽게 구현됐으나 메모리 초과를 맞았다. ^^
메모리가 어디서 많이 잡아먹힐까 고민해봤는데, 역시 아무래도 그래프를 저장하는 부분인 것 같았다.
예제 1번만 그려봐도 알수있다시피 하이퍼튜브 몇 개만 입력돼도 수많은 엣지들이 생긴다.
1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000이기 때문에 최대 노드의 수는 100,000개, 최대 엣지의 수는 1000,000개가 된다.
BFS의 시간복잡도는 O(v+e)이니 최악의 경우 꽤나 커진다.
처음에는 단순히 그래프를 저장하는 자료구조만 변경했었다.
list에서 dict, list에서 set 등 전전하다가 전부 메모리 초과가 났고...
GPT한테 물어봤다. 어느 부분에서 메모리 초과가 나겠느냐고
문제는 역시 그래프 저장이 맞았다.
단 자료구조만 변경할 것이 아니라 생각의 전환이 필요했다.
하이퍼튜브를 하나의 노드(역)이라고 생각해주는 것이다.
그러면 1-2-3 으로 이동한다면 1-ht-2-ht-3처럼 이동하게 되고 거리가 늘어나므로 거리를 2로 나눠서 계산해주면 된다.
이렇게 풀고 나서는 채점이 90%대까지 진행되었다.
그러고는 이번에는 틀렸습니다를 맞았다.
거의 다 풀었는데 마지막에 틀렸으니 특수한 경우의 수를 고려하지 않았구나 판단했다.
그리고 찾은 내가 고려하지 않은 부분은 두가지였다.
- 경로를 찾지 못한 경우
-1을 출력해야 하나bfs결과 // 2 + 1을 출력해서 0이 됨
➡️ bfs의 결과가 -1인 경우 그대로 출력, 아닌 경우 계산 후 출력 - 시작노드와 끝 노드가 일치하는 경우
1을 출력해야하나-1을 출력함
➡️ bfs가 시작하기 전 시작 노드와 끝 노드가 일치하는 경우 바로 1을 출력
코드
# 환승
# graph
import sys
from collections import deque
input = sys.stdin.readline
def bfs(g: list, n: int, m: int):
if n == 1:
return 1
s = 1
q = deque([(s, 1)])
vst = [0 for i in range(n + m + 1)]
vst[s] = 1
while q:
x, d = q.popleft()
nd = d + 1
for nx in g[x]:
if vst[nx]:
continue
if nx == n:
return nd
q.append((nx, nd))
vst[nx] = 1
# print(f"status of q now: {q}")
return -1
if __name__ == "__main__":
n, k, m = map(int, input().split())
g = [ set() for i in range(n+1+m) ]
for ht in range(1, m+1):
stations = list(map(int, input().split()))
g[n + ht].update(stations)
for s in stations:
g[s].add(n + ht)
res_bfs = bfs(g, n, m)
if res_bfs < 0:
print(res_bfs)
else:
result = res_bfs // 2 + 1
print(result)마무리
gpt도 참고하고, 질문 게시판도 참고하고 겨우겨우 푼 느낌이다.
참고로 아예 하이퍼튜브를 노드, 역을 엣지로 생각하고 푸는 방법도 있다고 하니 참고하면 좋겠다.
