난이도 : 골드 3
유형 : 최단 경로 / 다익스트라
링크 : https://www.acmicpc.net/problem/11779
구현 시간 : 30분
문제풀이
해당 문제를 해결하기 위해서 다익스트라 알고리즘을 사용하여 출발 도시에서 각 노드(도시)까지의 최소 시간을 구하고, 동시에 이전 방문 노드를 저장해야 한다.
이를 위해 인접한 노드를 방문하며 최소 시간을 distance[] 배열에 갱신하고, 이와 함께 이전 노드를 preN[] 배열에 저장한다.
이렇게 하면 특정 노드에 도달했을 때 해당 노드로 오기까지의 이전 노드를 추적할 수 있다.
이후 최단 거리를 출력하고, Stack을 사용하여 방문 순서를 역순으로 출력한다.
핵심은 다익스트라 알고리즘에서 distance[] 배열을 갱신할 때, 이전 노드를 preN[] 배열에 함께 기록하여 경로 추적이 가능하다는 것을 이해하는게 중요하다.
1차 시도 - 통과
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
static StringTokenizer st;
static int N;
static int M;
static int start;
static int end;
static int[] distance, preN;
static List<Node>[] list;
static class Node implements Comparable<Node> {
int idx;
int cost;
public Node(int idx, int cost) {
this.idx = idx;
this.cost = cost;
}
@Override
public int compareTo(Node o) {
return Integer.compare(cost, o.cost);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
distance = new int[N + 1]; // 노드 별 최소 거리 저장
preN = new int[N + 1]; // 이전 방문 노드 저장
list = new List[N + 1]; // 노드 연결, 비용 정보 저장
Arrays.fill(distance, Integer.MAX_VALUE);
for (int i = 1; i < N + 1; i++) {
list[i] = new ArrayList<>();
}
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());
list[from].add(new Node(to, cost));
}
st = new StringTokenizer(br.readLine());
start = Integer.parseInt(st.nextToken());
end = Integer.parseInt(st.nextToken());
dijkstra();
System.out.println(distance[end]);
// 역추적 시작
Stack<Integer> stack = new Stack<>();
stack.push(end);
int cnt = 1;
while (preN[end] != 0) {
cnt++;
stack.push(preN[end]);
end = preN[end];
}
System.out.println(cnt);
while (!stack.isEmpty()) {
System.out.print(stack.pop() + " ");
}
}
public static void dijkstra() {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(start, 0));
distance[start] = 0;
while(!pq.isEmpty()) {
Node node = pq.poll();
int idx = node.idx;
int cost = node.cost;
if (cost > distance[idx]) {
continue;
}
for (Node next : list[idx]) {
int nextIdx = next.idx;
int newCost = cost + next.cost;
if (distance[nextIdx] > newCost) {
distance[nextIdx] = newCost;
pq.offer(new Node(nextIdx, newCost));
// 이전 방문 노드 추가
preN[nextIdx] = idx;
}
}
}
}
}
'PS > 백준' 카테고리의 다른 글
[BOJ/Gold5] 15686번 치킨 배달 - JAVA[자바] (1) | 2025.01.15 |
---|---|
[BOJ/Gold3] 1005번 ACM Craft - JAVA[자바] (0) | 2025.01.09 |
[BOJ/Silver1] 2156번 포도주 시식 - JAVA[자바] (0) | 2025.01.05 |
[BOJ/Silver1] 9465번 스티커 - JAVA[자바] (2) | 2025.01.04 |
[BOJ/Silver3] 2193번 이친수 - JAVA[자바] (1) | 2025.01.04 |