풀이 방법
전형적인 다익스트라 문제이다.
우선순위 큐를 이용한 다익스트라 알고리즘을 구현해서 풀이했다.
2021.10.01 - [분류 전체보기] - 최단 경로 알고리즘 (다익스트라, 벨만-포드, 플로이드-워셜)
내 코드
package com.company;
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
class Node implements Comparable<Node> {
private int distance;
private int index;
public Node(int index, int distance) {
this.distance = distance;
this.index = index;
}
public int getDistance() {
return distance;
}
public int getIndex() {
return index;
}
@Override
public int compareTo(Node other) {
if (this.distance < other.getDistance())
return -1;
return 1;
}
}
public class Main {
static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
static int v, e, start;
static int[] d;
static void dijkstra(int start) {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(start, 0));
d[start] = 0;
while (!pq.isEmpty()) {
Node node = pq.poll();
int dist = node.getDistance();
int nowIndex = node.getIndex();
if (d[nowIndex] < dist)
continue;
for (int i = 0; i < graph.get(nowIndex).size(); i++) {
int cost = d[nowIndex] + graph.get(nowIndex).get(i).getDistance();
if (cost < d[graph.get(nowIndex).get(i).getIndex()]) {
d[graph.get(nowIndex).get(i).getIndex()] = cost;
pq.offer(new Node(graph.get(nowIndex).get(i).getIndex(), cost));
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
v = Integer.parseInt(st.nextToken());
e = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
start = Integer.parseInt(st.nextToken());
d = new int[v + 1];
for (int i = 0; i <= v; i++) {
graph.add(new ArrayList<Node>());
}
Arrays.fill(d, (int) 1e9);
for (int i = 0; i < e; i++) {
st = new StringTokenizer(br.readLine());
graph.get(Integer.parseInt(st.nextToken())).
add(new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
}
dijkstra(start);
for (int i = 1; i < d.length; i++) {
if (d[i] == (int) 1e9)
System.out.println("INF");
else
System.out.println(d[i]);
}
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
저울 - 10159번 (0) | 2021.10.01 |
---|---|
백도어 - 17396번 (0) | 2021.10.01 |
동전 2 - 2294번 (0) | 2021.09.29 |
1로 만들기 - 1463번 (0) | 2021.09.29 |
트리의 부모 찾기 - 11725번 (0) | 2021.09.24 |