풀이 방법
모든 최단 경로를 구할 수 있는 플로이드 와샬 방법으로 풀이 했다.
처음 지나는 경로를 찾는 것보다 마지막 지나는 경로를 찾는 것이 수월하다고 판단되어 맨 처음 지나가는 경로를 구하는 것이 아닌 마지막 경로를 구해서 출력할 때 반대로 뒤집는 방법을 사용했다.
내 코드
package com.company;
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[][] array = new int[N + 1][M + 1];
int[][] way = new int[N + 1][M + 1];
for (int i = 0; i <= N; i++) {
Arrays.fill(array[i], 10000);
}
for (int i = 1; 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());
array[a][b] = c;
array[b][a] = c;
way[a][b] = a;
way[b][a] = b;
}
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 (array[i][j] > array[i][k] + array[k][j]) {
array[i][j] = array[i][k] + array[k][j];
way[i][j] = way[k][j];
}
}
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (way[i][j] == 0)
System.out.print("- ");
else {
System.out.print(way[j][i] + " ");
}
}
System.out.println();
}
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
독서실 거리두기 - 20665번 (0) | 2021.10.27 |
---|---|
뱀과 사디리 게임 - 16928번 (0) | 2021.10.27 |
점수따먹기 - 1749번 (0) | 2021.10.25 |
색종이와 가위 - 20444번 (0) | 2021.10.25 |
네트워트 연결 - 1922번 (0) | 2021.10.22 |