백준 1719번
https://www.acmicpc.net/problem/1719
문제
생각하기
-
최단 경로 구하기 문제.
-
전체 노드의 최단 경로를 구하는 문제이므로, 플로이드 워셜이 효율적
동작
while (!pQue.isEmpty()) {
Node current = pQue.poll();
if (dist[current.num] < current.time) continue;
if (visited[current.num]) continue;
visited[current.num] = true;
for (Node next : adjList.get(current.num)) {
if (dist[next.num] > dist[current.num] + next.time) {
dist[next.num] = dist[current.num] + next.time;
pQue.offer(new Node(next.num, dist[next.num]));
if (num == current.num) {
// 이전 노드가 출발 노드 일 경우, 다음 노드 번호를 넣는다.
ans[num][next.num] = next.num;
} else {
// 그 외의 경우 다음 노드에는 이전의 부모 노드 번호를 넣는다. (바로 이전의 거쳐온 곳)
ans[num][next.num] = ans[num][current.num];
}
}
}
}
ans 이전 방문 노드 배열을 만들때 출발 노드num과 현재 노드 current.num이 같을 때는 다음 경로 next.num을 넣으면 된다.
그리고 그 외의 경우에는 다음 노드 next.num에 current노드를 대입해주면 된다.
전체 N개의 노드 최단 경로를 구해야하므로 플로이드 워셜이 보다 효율적이라고 볼 수 있다.
최단 경로를 기록하는 방법은
path = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (i != j) {
path[i][j] = j;
}
}
}
i에서 j로 가는 경로의 다음 노드를 j로 설정하기 위함입니다.
기본적인 설정 입니다.
이후 최단 경로 기록은 path에서 플로이드 워셜을 통해 최단 거리를 갱신하는 과정에서 이동 경로를 기록하면 됩니다.
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (i == j) continue;
if (arr[i][j] > arr[i][k] + arr[k][j]) {
arr[i][j] = arr[i][k] + arr[k][j];
path[i][j] = path[i][k];
}
}
}
}
path[i][j] = path[i][k]; i에서 j로 이동할 때 i -> k -> j 순으로 이동하는 경로에서 [i][k]의 이전 경로가 기록 되어야 하므로 path[i][k]를 저장합니다.
결과
코드
다익스트라
import java.io.*;
import java.util.*;
public class Main {
// input
private static BufferedReader br;
// variables
private static int N, M;
private static int[][] path;
private static List<List<Edge>> adjList;
private static final int INF = 1_000_000_1;
private static class Edge implements Comparable<Edge> {
int num;
int dist;
private Edge(int num, int dist) {
this.num = num;
this.dist = dist;
}
@Override
public int compareTo(Edge o) {
return dist - o.dist;
}
} // End of Edge class
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
input();
bw.write(solve());
bw.close();
} // End of main()
private static String solve() {
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= N; i++) {
dijkstra(i);
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (i == j) {
sb.append('-').append(' ');
} else {
sb.append(path[i][j]).append(' ');
}
}
sb.append('\n');
}
return sb.toString();
} // End of solve()
private static void dijkstra(int start) {
PriorityQueue<Edge> pque = new PriorityQueue<>();
int[] dists = new int[N + 1];
Arrays.fill(dists, INF);
boolean[] isVisited = new boolean[N + 1];
pque.offer(new Edge(start, 0));
dists[start] = 0;
while (!pque.isEmpty()) {
Edge cur = pque.poll();
if (dists[cur.num] < cur.dist) continue;
if (isVisited[cur.num]) continue;
isVisited[cur.num] = true;
for (Edge next : adjList.get(cur.num)) {
if (dists[next.num] > dists[cur.num] + next.dist) {
dists[next.num] = dists[cur.num] + next.dist;
pque.offer(new Edge(next.num, dists[next.num]));
if (start == cur.num) {
path[start][next.num] = next.num;
} else {
path[start][next.num] = path[start][cur.num];
}
}
}
}
} // End of dijkstra()
private static void input() throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
adjList = new ArrayList<>();
path = new int[N + 1][N + 1];
for (int i = 0; i <= N; i++) {
adjList.add(new ArrayList<>());
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
adjList.get(a).add(new Edge(b, c));
adjList.get(b).add(new Edge(a, c));
}
} // End of input()
} // End of Main class
플로이드 워셜
import java.io.*;
import java.util.StringTokenizer;
public class Main {
// input
private static BufferedReader br;
// variables
private static int N, M;
private static int[][] arr, path;
private static final int INF = 10_000_001;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
input();
bw.write(solve());
bw.close();
} // End of main()
private static String solve() {
StringBuilder sb = new StringBuilder();
floyd();
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (i == j) {
sb.append('-').append(' ');
} else {
sb.append(path[i][j]).append(' ');
}
}
sb.append('\n');
}
return sb.toString();
} // End of solve()
private static void floyd() {
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (i == j) continue;
if (arr[i][j] > arr[i][k] + arr[k][j]) {
arr[i][j] = arr[i][k] + arr[k][j];
path[i][j] = path[i][k];
}
}
}
}
} // End of floyd()
private static void input() throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N + 1][N + 1];
path = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (i != j) {
arr[i][j] = INF;
path[i][j] = j;
}
}
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
arr[a][b] = c;
arr[b][a] = c;
}
} // End of input()
} // End of Main class
