문제
문제 시간 제한 1초, 메모리 제한 256MB
n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다.
입력
첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.
그리고 m+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다.
출력
최소 비용
최소 비용의 루트에 포함된 도시의 개수
도시를 순서대로 출력
풀이
최소 비용만이 아니라, 최소 비용을 위해 지나쳐온 도시의 개수와 도시를 순서대로 출력하는 부분이 추가된 다익스트라 문제이다.
static class Bus implements Comparable<Bus>{
int to;
int cost;
Bus(int to, int cost) {
this.to = to;
this.cost = cost;
}
@Override
public int compareTo(Bus o) {
return this.cost - o.cost;
}
}
static void solution(int start) {
PriorityQueue<Bus> pq = new PriorityQueue<>();
cost[start] = 0;
pq.offer(new Bus(start, 0));
while(!pq.isEmpty()) {
Bus current = pq.poll();
if(current.cost > cost[current.to]) continue; // 중복 계산 X
for(Bus next : buses[current.to]) {
if(cost[current.to] + next.cost < cost[next.to]) {
route[next.to].add(current.to);
cost[next.to] = cost[current.to] + next.cost;
pq.add(new Bus(next.to, cost[next.to]));
}
}
}
}여기까지는 금방 작성할 수 있었는데...
static ArrayList<Integer>[] route; 변수를 선언하고 여기에 통과해온 도시들을 입력해두고, 개수는 size+1로 출력, 마지막 도시는 그냥 b를 출력하면 되려나? 하고 작성해봤는데... 통과해온 도시를 갱신할 때 route[next.to].add(current.to);로 그냥 바로 전 도시만 갱신하게 작성했으니까 모든 최단 경로가 누적되지 않았다.
어떻게 해야할지 한참 고민했는데... 의외로 별 거 아니었다.
route[next.to] = new ArrayList<>(route[current.to]);
route[next.to].add(current.to);이렇게 다음 route에 기존 루트를 아예 복사해서 넣어주고 current.to까지 추가해주면 된다.
전체 코드는 아래와 같다.
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int M;
static ArrayList<Bus>[] buses;
static int[] cost;
static ArrayList<Integer>[] route;
static class Bus implements Comparable<Bus>{
int to;
int cost;
Bus(int to, int cost) {
this.to = to;
this.cost = cost;
}
@Override
public int compareTo(Bus o) {
return this.cost - o.cost;
}
}
static void solution(int start) {
PriorityQueue<Bus> pq = new PriorityQueue<>();
cost[start] = 0;
pq.offer(new Bus(start, 0));
while(!pq.isEmpty()) {
Bus current = pq.poll();
if(current.cost > cost[current.to]) continue;
for(Bus next : buses[current.to]) {
if(cost[current.to] + next.cost < cost[next.to]) {
route[next.to] = new ArrayList<>(route[current.to]);
route[next.to].add(current.to);
cost[next.to] = cost[current.to] + next.cost;
pq.add(new Bus(next.to, cost[next.to]));
}
}
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
// n개의 도시
// 다른 도시에 도착하는 m개의 버스
// a -> b로 가는 버스 비용 최소화
// 시작점에서 도착점으로의 경로가 항상 존재
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
cost = new int[N+1];
route = new ArrayList[N+1];
buses = new ArrayList[N+1];
for(int i=0; i<=N; i++) {
route[i] = new ArrayList<>();
cost[i] = Integer.MAX_VALUE;
}
for(int i=0; i<=N; i++) {
buses[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());
buses[from].add(new Bus(to, cost));
}
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
solution(a);
bw.write(cost[b] + "\n");
bw.write((route[b].size()+1) + "\n");
for(int x : route[b]) {
bw.write(x + " ");
}
bw.write(b + "");
bw.flush();
bw.close();
br.close();
}
}
문제를 풀며
맞기는 했지만... 사실 조금 찔리는 부분이 있다. 마지막에 b를 그냥 수동으로 추가해주고 size()를 하나 늘려 작성했기 때문에... 완전히 제대로 된 방법으로 푼 느낌은 아니었다. 제출 후 route[next.to]를 갱신할 때 next.to도 같이 추가해주면 되지 않나?라는 생각이 들어서 추가하는 부분을 넣고 예제를 돌려봤더니 오답이 나왔다. 그리고 굳이 모든 도시들의 최단경로를 ArrayList<>[]로 일일히 갱신할 필요 없이, 도착점까지의 최단 경로만 찍으면 되는 거 아닌가?라는 생각도 들고...
그래서 다른 분들의 풀이를 검색하여 차이점을 찾아보았다.
내가 가졌던 두 찜찜함을 모두 풀어주는 풀이가 있었는데!! 이 코드[https://chbong.tistory.com/153]였다. next.to의 값을 갱신할 때, 배열에 바로 직전(최단 경로로 올 때의 전 도시)를 저장해둔다. 그리고 스택을 사용해 도착점까지의 경로를 출력한다. 깔끔하고 스택 활용이 너무 좋았다!! 나라면 for문과 if문으로 돌리면서 찾았을 거 같은데...
다른 분의 코드를 읽고 나니 예전에 풀었던 문제가 생각났다. 특정 지점 A까지 가는데 드는 최단 경로는 다른 지점에게도 최단 경로라는 개념을 바탕으로 풀었던 문제가 있었다. 이 개념을 잘 기억해두어야 할 것 같다..! 그 문제 풀이를 다시 읽어보고 싶은데 몇 번 문제인지 기억이 안 난다. 이해하느라 애 먹었던 걸로 기억하는데... 블로그로 써둘 걸...ㅜㅜ 찾으면 추가해둬야겠다.