산 넘어 산 개발일지

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

풀이 키워드 다익스트라(Dijkstra) 일반적인 다익스트라 알고리즘으로 풀리는 문제이다. 한 노드에서 각 노드까지 갈 수 있는 최단거리를 구해야 하며, 각 노드마다 가중치가 각각 다르므로 DFS, BFS로는 풀 수 없고 다익스트라로 풀어야 한다는 것을 알 수 있다. 우선순위 큐(PriorityQueue)를 사용해서 풀면 훨씬 빠르고 편리하다. 우선순위 큐를 사용하면 현재 큐를 최적의 방법으로 정렬하여 가장 거리가 짧은 노드부터 검사할 수 있게 해주며, 이 때문에 각 노드의 방문여부를 체크할 필요가 사라진다. 푸는 방식을 간단하게 소개하면 다음과 같다. 도시들의 그래프인 arr[]이 있고, 시작점에서 각 도시까지의 거리를 나타낸 dist[]가 있다. dist[]는 시작점은 0으로, 나머지는 Inf 값으로..