Binceline

크루스칼 알고리즘과 Prim's 알고리즘으로 해결할 수 있다. 이걸 MST (Minimal Spanning Tree) 알고리즘이라고 한다. 난 Prim's 알고리즘으로 해결했다. 다익스트라 알고리즘과 유사하지만 '정점으로 가는 최단거리'를 계속 갱신해 줄 필요가 없다.그리고 다익스트라 알고리즘은 정점을 연결하는 간선의 방향이 존재하는데, MST는 그저 '연결되었는가?' 이다. pq : 현재 위치에서 갈 수 있는, 혹은 지금까지 갈 수 있었던 정점들을 거리순으로 정렬해 놓는 우선순위 큐dist : 스패닝 트리를 만드는 최소비용을 누적해나갈 변수 1. 큐에서 하나 빼고 이미 갔던 곳인지 검사한다. 이미 갔던 곳이라면 반복.2. 이전 위치로부터 현재 위치로 가는 거리를 dist에 추가함.3. 현재 위치에서 갈..

다익스트라 알고리즘 나무위키 시작점으로부터 갈 수 있는 모든 경로에 대한 최단거리를 구한다. 필요했던 것- map : 간선정보를 저장할 map- v : 이미 방문했는지를 위한 visit array- d : 시작점으로부터 정점까지의 거리 정보를 가지고 있는 distance array- pq : 현재 갈 수 있는(그리고 갈 수 있었던) 정점들을 담아 둘 priority queue. 정점과 거리 쌍으로 저장. 코드 가독성을 위해 pq에 첫 번째 위치 (시작점)을 미리 입력해 놓고 했음. 1. pq에서 하나 pop하고 이미 방문했던 곳인지 visit array 검사. 이미 방문했으면 다시 1번 반복.2. 주변 경로 확인 후 map을 보면서 [원래 알고 있던 목적지까지의 거리]와 [현재 지점까지의 거리 + 목적지..