문제출처: https://www.acmicpc.net/problem/1719
1719번: 택배
명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하
www.acmicpc.net
문제이해
목표
그래프 -> 노드 : 집하장, 간선 : 경로
예를 들어 4행 5열의 6은 4번 집하장에서 5번 집하장으로 최단 경로를 통해 가기 위해서는 제일 먼저 6번 집하장으로 이동해야 한다는 의미이다.
이와 같은 경로표를 구하는 프로그램을 작성하시오.
풀이
다익스트라를 이용한 기본문제이다.
모든 노드가 첫 번째 노드가 되어 n번의 다익스트라를 진행한다.
초기(루트 노드 -> 다음노드): 다익스트라를 진행하면서 제일먼저 확장된 다음노드를 기억해줘야 한다.
그 외(다음노드 -> 다음노드): 전 노드에서 기억한 노드를 기억하면 된다.
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
// https://www.acmicpc.net/problem/1719
public class 택배 {
static class Edge {
int dest;
int price;
public Edge(int dest, int price) {
this.dest = dest;
this.price = price;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] strArr = br.readLine().split(" ");
int N = Integer.parseInt(strArr[0]);
int E = Integer.parseInt(strArr[1]);
// 인접리스트 만들기
int[][] answer = new int[N + 1][N + 1];
int[] dp = new int[N + 1];
ArrayList<Edge>[] adjList = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
adjList[i] = new ArrayList<>();
}
for (int i = 0; i < E; i++) {
strArr = br.readLine().split(" ");
int start = Integer.parseInt(strArr[0]);
int dest = Integer.parseInt(strArr[1]);
int price = Integer.parseInt(strArr[2]);
adjList[start].add(new Edge( dest, price));
adjList[dest].add(new Edge( start, price));
}
// 다익스트라
final int MAX = 200001;
PriorityQueue<Edge> pq = new PriorityQueue<Edge>((a, b) -> {
return a.price - b.price;
});
for (int start = 1; start <= N; start++) { // 모든 노드가 시작점이 되봄. 다익스트라
Arrays.fill(dp, MAX);
dp[start] = 0;
pq.add(new Edge(start, 0));
while (!pq.isEmpty()) {
Edge edge = pq.poll();
if (dp[edge.dest] < edge.price) {
continue;
}
for (Edge nextEdge : adjList[edge.dest]) {
int nextPrice = edge.price + nextEdge.price;
if (nextPrice < dp[nextEdge.dest]) {
dp[nextEdge.dest] = nextPrice;
pq.add(new Edge(nextEdge.dest, nextPrice));
if(answer[start][edge.dest] != 0){
answer[start][nextEdge.dest] = answer[start][edge.dest];
} else{
answer[start][nextEdge.dest] = nextEdge.dest;
}
}
}
}
}
// 출력
StringBuilder sb = new StringBuilder();
for (int row = 1; row <= N; row++) {
for (int col = 1; col <= N; col++) {
if (row == col) {
sb.append("- ");
} else {
sb.append(answer[row][col] + " ");
}
}
sb.append("\n");
}
System.out.println(sb);
}
}
문제 복기
1. dp배열은 모든 dijkstra 결과를 기억할 필요없어서 1차원 배열로 설정해도 된다.
2. answer 배열도 마찬가지다, dijkstra가 한번끝나면 그냥 StringBuilder로 값을 버퍼에 담아놓으면 된다.
3. 다익스트라를 PriorityQueue와 인접리스트로 구현했기 때문에, 노드에 들어오는 가장 첫번째 간선경로가 이미 그 노드까지의 최소거리가 된다. 이를 이용해서 이렇게 가지치기해도 되는 것이다.
2번째 방문해도 비용 검사(if (nextPrice < dp[nextEdge.dest]) )에 걸려서 갱신되지 않는다.
if(answer[start][edge.dest] != 0){
answer[start][nextEdge.dest] = answer[start][edge.dest];
} else{
answer[start][nextEdge.dest] = nextEdge.dest;
}