이번 문제는 다익스트라 알고리즘이다. 예전에 자료구조나 알고리즘 시간때 잠깐 이론으로 배운적은 있는데 문제를 통해 접한 것은 처음이다...
이 문제를 먼저 파악할때 최소 거리를 찾아야한다에 주목해서 다익스트라 알고리즘을 생각해 내야 하며 자료구조는 primary queue를 사용해야한다... 이유는 pop을 할때 최소 거리의 경우를 내뱉고 그것을 가지고 생각해내는 방식이기 때문이다
처음에는 다익스트라로 짜지 않고 내 방식대로 queue를 활용한 bfs느낌으로 짜보았다.
from collections import deque
import sys
input = sys.stdin.readline
N = int(input())
M = int(input())
matrix = dict()
for _ in range(M):
a, b, c = map(int, input().split())
if a in matrix:
matrix[a].append((b, c))
else:
matrix[a] = [(b, c)]
if b in matrix:
matrix[b].append((a, c))
else:
matrix[b] = [(a, c)]
start, end = map(int, input().split())
answer = 999999
dq = deque([(start, 0)])
visit = set()
while dq:
a, b = dq.popleft()
if a == end:
answer = min(answer, b)
for i, j in matrix[a]:
if (a, i) not in visit:
visit.add((a, i))
temp = b + j
dq.append((i, temp))
print(answer)처음에 visit을 리스트 구조로 짰는데 이때 맹점은 출발 노드가 달라도 도착 노드가 같을 때 방문한 방식으로 판별된다는 점이다... 그래서 set함수로 출발을 추가해 구별을 해 줬지만 결과적으로 이 방식은 전체를 탐색하며 시간단축을 할 수 없는 O(n2) 방식이다.
다익스트라는 visit에 최소 거리를 저장해 그 거리보다 크면 탐색을 안하는 방식이었으며 위 문제를 해결할 수 있어서 놀라웠다.
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
N = int(input())
M = int(input())
inf = 100000000
matrix = dict()
matrix = [[] for _ in range(N + 1)]
for _ in range(M):
a, b, c = map(int, input().split())
matrix[a].append((c, b))
visit = [inf]*(N+1)
start, end = map(int, input().split())
pq = list()
heappush(pq, (0, start))
visit[start] = 0
while pq:
d, x = heappop(pq)
if visit[x] < d:
continue
for nd, nx in matrix[x]:
new_distance = d+nd
if visit[nx] > new_distance:
heappush(pq, (new_distance, nx))
visit[nx] = new_distance
print(visit[end])다른 블로그를 참고해서 코드를 짰고 궁금한 것은 처음에 그래프를 짤 때 나는 dictionary로 짰었는데 list로 짠 점이다... key가 순서가 있는 숫자가 아니면 불가능 한것 아닌가? 물론 defaultdict로 짠 사람도 있어서 그러려니 했지만 또 궁금한점은 다익스트라 알고리즘은 방향 그래프에서만 가능하다고 한다... 문제에서 어떻게 방향 그래프만 가능하다고 파악하고 자신있게 저렇게 그래프를 만들었는지도 어려운 부분이다.
일단 다익스트라 알고리즘은 방식은 사람마다 다양한거 같긴 한데... 핵심은 우선순위 큐를 사용하며 최소 거리를 visit에 넣어주는 방식이다.
내가 참고해서 짠 위 코드는 거리가 visit의 x보다 작으면 넘기고 또한 새로운 거리를 찾았을 때 그 거리가 기존꺼랑 비교해서 작을 경우만 heap에 넣고 visit에 기록한다...
다익스트라 알고리즘을 내것으로 만들기를 꼭 해야겠다...
