문제
n개의 도시가 있고 버스가 m개 있을 때, 출발 도시에서 도착 도시까지 가는 최소 비용과 그 경로를 구하는 문제이다. 버스는 단방향이다.
입력
첫째 줄에 도시의 개수 n (1 ≤ n ≤ 1,000), 둘째 줄에 버스의 개수 m (1 ≤ m ≤ 100,000)이 주어진다. 다음 m개의 줄에 각 버스의 출발 도시, 도착 도시, 비용 (1 ≤ 비용 ≤ 100,000)이 주어진다. 마지막 줄에 출발 도시와 도착 도시가 주어진다.
출력
첫째 줄에 출발 도시에서 도착 도시까지 가는 최소 비용을 출력한다. 둘째 줄에 경로에 포함되는 도시의 개수를 출력한다. 셋째 줄에 경로를 순서대로 출력한다.
예제
입력
5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5출력
4
3
1 3 5풀이
핵심 아이디어: 다익스트라 알고리즘으로 최단 경로를 구하면서, 각 노드의 이전 노드(pre 배열)를 기록해 경로를 역추적한다.
dist[i]를 출발 노드에서 노드 i까지의 최소 비용으로 초기화(Integer.MAX_VALUE)한다.- 우선순위 큐를 사용해 다익스트라를 수행하며, 더 짧은 경로로 노드를 방문할 때
pre[next] = cur로 이전 노드를 기록한다. - 도착 노드에 처음 도달하면 탐색을 종료한다.
- 역추적:
E에서 시작해pre[E]를 따라가며pre[node] == 0이 될 때까지 반복하면 경로를 역순으로 얻는다. list를 역순으로 출력한다.
pre 배열의 초기값이 0이고 노드 번호가 1부터 시작하므로, pre[node] == 0을 종료 조건으로 사용한다.
코드
import java.util.*;
import java.io.*;
public class Day374BOJ11779최소비용구하기2 {
static int N, M, S, E;
static ArrayList<Integer> list;
static ArrayList<ArrayList<Node>> graph;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
graph = new ArrayList<ArrayList<Node>>();
for (int i = 0; i < N + 1; i++)
graph.add(new ArrayList<>());
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
graph.get(u).add(new Node(v, c));
}
st = new StringTokenizer(br.readLine());
S = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
int[] dist = new int[N + 1];
for (int i = 0; i <= N; i++)
dist[i] = Integer.MAX_VALUE;
dist[S] = 0;
int[] pre = new int[N + 1];
PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.cost, o2.cost));
pq.offer(new Node(S, 0));
while (!pq.isEmpty()) {
Node cur = pq.poll();
if (cur.idx == E) {
sb.append(dist[E] + "\n");
break;
}
if (cur.cost > dist[cur.idx])
continue;
for (int i = 0; i < graph.get(cur.idx).size(); i++) {
Node next = graph.get(cur.idx).get(i);
if (dist[next.idx] > cur.cost + next.cost) {
dist[next.idx] = cur.cost + next.cost;
pre[next.idx] = cur.idx;
pq.offer(new Node(next.idx, dist[next.idx]));
}
}
}
list = new ArrayList<>();
while (true) {
if (pre[E] == 0)
break;
list.add(E);
E = pre[E];
}
list.add(S);
sb.append(list.size() + "\n");
for (int i = list.size() - 1; i >= 0; i--) {
sb.append(list.get(i) + " ");
}
System.out.println(sb);
br.close();
}
static class Node {
int idx, cost;
public Node(int idx, int cost) {
super();
this.idx = idx;
this.cost = cost;
}
}
}복잡도
- 시간: O((V + E) log V) — V = n(도시 수), E = m(버스 수), 우선순위 큐 기반 다익스트라
- 공간: O(V + E) — 인접 리스트 그래프, dist 배열, pre 배열