⭐문제링크
다익스트라 오랜만에 풀어보니 안풀렸다
역시 공부는 복습이 중요하다
1. 다익스트라 기본 접근법
다익스트라의 기본 접근법은 간단하다
- Node 클래스를 만든다.
- 우선순위 큐에 노드를 넣는다.
(대신 값이 변하는 노드들만 넣어준다!) - 우선순위 큐가 빌 때까지 경로 배열을 업데이트 해준다.
2. 코드
2-1. Node 클래스
static class Node implements Comparable<Node> {
int to;
int cost;
public Node(int to, int cost) {
this.to = to;
this.cost = cost;
}
@Override
public int compareTo(Node o) {
return this.cost-o.cost;
}
}해당 클래스는 우선순위 큐에 넣어야 하는데, 우선순위큐는 Comparable 인터페이스를 정의해야 함을 잊지 말자
음수 반환되면 무조건 this. 객체를 앞에 세우고, 양수 반환되면 비교 객체를 앞에 세운다.
2-2. 입력 및 초기화 부분
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
List<Node> [] dijkstra = new List[N+1];
for(int i = 0; i < dijkstra.length; i++) {
dijkstra[i] = new ArrayList<>();
}
int [] route = new int[N+1];
Arrays.fill(route, 1000000001);
for(int i=0; i<M; i++) {
st=new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
dijkstra[from].add(new Node(to, cost));
}
st = new StringTokenizer(br.readLine());
int departure = Integer.parseInt(st.nextToken());
int arrival = Integer.parseInt(st.nextToken());
PriorityQueue<Node> pq = new PriorityQueue<>();
.
.
.
3. 다익스트라 반복문
pq.add(new Node(departure, 0));
route[departure]=0;
while (!pq.isEmpty()) {
Node now = pq.poll();
if(route[now.to] < now.cost) continue;
//이미 더 짧은 경로로 처리된 노드를 건너뛰어 불필요한 처리를 방지합니다.
for(int i=0; i<dijkstra[now.to].size(); i++){
Node next = dijkstra[now.to].get(i);
//최단 경로 추정을 업데이트하고 그래프의 탐색을 계속할 수 있도록 합니다
if(now.cost+next.cost < route[next.to]){
route[next.to] = now.cost+next.cost;
pq.add(new Node(next.to, route[next.to]));
}
}
}
System.out.println(route[arrival]); //최종 출력
}
다익스트라 반복문에 대한 부분을 하나하나 살펴보면
✔️ 1. 큐에 도착지 노드 삽입
pq.add(new Node(departure, 0));
route[departure]=0; //출발지의 경로는 항상 0✔️ 2. 큐에서 노드를 하나 꺼냄
while (!pq.isEmpty()) {
Node now = pq.poll();
if(route[now.to] < now.cost) continue;
//이미 더 짧은 경로로 처리된 노드를 건너뛰어 불필요한 처리를 방지합니다.
.
.
.
여기서 중요한 점은 if문이다. 현재 우선순위 큐에서 꺼낸 노드는 이전에서 처리된 해당 노드의 경로를 의미한다.
그런데 해당 노드가 poll 되기 전, 이미 route[answer.to]에 대한 값은 최적화가 되어있는 상태일 수도 있다.
이런 경우 다익스트라 알고리즘을 진행하지 않아도 되기에 continue를 사용해 빠르게 넘긴다.
✔️3. cost 배열을 갱신해준다.
.
.
.
for(int i=0; i<dijkstra[now.to].size(); i++){
Node next = dijkstra[now.to].get(i);
//최단 경로 추정을 업데이트하고 그래프의 탐색을 계속할 수 있도록 합니다
if(now.cost+next.cost < route[next.to]){
route[next.to] = now.cost+next.cost;
pq.add(new Node(next.to, route[next.to]));
}
}이전 if 문을 통과했다 하더라도, 당연히 현재 우선순위에서 반환된 가장 작은 노드인 now까지의 cost 값과, now가 가리키고 있는 그 다음 노드인 next까지, 즉 now->next 까지의 cost 값을 더한 값을 기존의 route[]과 비교해야 한다.
즉
- 출발점->next->now 비용 (경유 O 비용)
- 출발점->now (경유 X 비용)
을 비교해서 더 싼 값을 route 배열에 갱신한다는 코드이다.
여기서 만약 값이 바뀐다면, 해당 노드는 더 갱신할 여지가 있으므로 우선순위 큐에 넣어줘서 다시 한 번 더 확인해주게 된다.
