Binceline

DFS 깊이 우선 탐색. 말 그대로 현재 위치에서 갈 수 있는 곳 중 짧은 곳으로 최대한 깊게 들어간다. 들어가다가 막히면 다시 뒤로 돌아와서 갈 수 있는 곳으로 감. 하지만 만약 그래프의 깊이가 커질수록 부하도 커진다. BFS 너비 우선 탐색 이건 과거, 그리고 현재에서 갈 수 있던 곳 중 가장 짧은 곳으로 간다. DFS, BFS는 이전 값들을 축적하지 않기 때문에 간선을 이동하는 비용(가중치)이 1이어야 한다. (비용이 같아야 한다는 것) 다익스트라 알고리즘 너비 우선 탐색이다. 다익스트라 알고리즘은 이 (가중치)들을 점점 축적해 나간다. 축적한다는 건 다이나믹 방식을 사용한다는 것이다. 프림 알고리즘 프림 알고리즘은 MST(최소 스패닝 트리) 알고리즘이라고 하는데, 각 정점을 연결하는 간선들을 최소..

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