산 넘어 산 개발일지

풀이 키워드 다익스트라 다익스트라로 푸는 것을 안다면 그렇게 어려운 문제는 아니였다. 그러나 다익스트라로 풀어야 한다는 것을 눈치채는 것이 문제라면 문제인 그런 유형이였다. 우선 그래프 탐색에는 유명한 3가지 DFS, BFS, Dijkstra가 있다. 우선 대부분의 문제에서 2차원 형식의 지도(?)처럼 주어지면 대개 DFS/BFS로 푸는 경우가 많다. 반대로, Dijkstra의 경우 대부분 이렇게 2차원 지도로 주어지지 않고 각 노드간의 연결 정보와 그 가중치가 주어진다. 이렇게 주어지는 이유는, DFS/BFS와 Dijkstra의 가장 큰 차이점은 노드간 가중치가 같은지 여부이기 때문이다. DFS/BFS의 경우 모든 노드간의 가중치가 같고, 우리가 찾아내야 하는 정답의 기준은 "얼마나 적은 수의 노드를 ..