[BOJ]11780번 플로이드2 (Java)
문제 (Gold 2)
풀이
모든 경로에 대한 최소 비용을 구해야 하므로 '플로이드-워샬 알고리즘' 사용!
최소 비용 외, 경로에 대한 내용도 저장해야 하므로 이차원배열 변수 하나 더 선언
map[i][j]: i -> j 경로의 최소 비용 저장
path[i][j]: i에서 출발해서 j까지 도착하기 직전에 들르는 도시
바로 오는 길(map[i][j])보다 경로 k를 거쳐서 오는 길(map[i][k] + map[k][j])이 더 빠를 경우,
최소 비용 저장 및 도착점 j로 가기 전에 들른 곳 저장!
경로 i -> j가 i->k->j가 되었으므로, path[i][j]는 j에 도착하기 직전 들른 곳인 path[k][j]로 저장
경로 출력 로직
i->j 경로라고 할 경우,
j전에 들렸던 곳을 계속해서 타고 가서 i를 만날때까지 스택에 넣으며 반복하는 로직
\=> 마지막 도착점부터 시작점까지 타고 거꾸로 타고 감
코드
package shortestPath;
import java.util.*;
import java.io.*;
public class Main_11780_플로이드 {
static final int INF = 10000001;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
int[][] map = new int[n+1][n+1]; // 최단경로 저장
int[][] path = new int[n+1][n+1]; // 도착점으로 가기 직전에 들린 점 저장
for(int i = 0 ; i < n+1 ; i++){
for(int j = 0 ; j < n + 1 ; j++){
if(i == j){
map[i][j] = 0;
path[i][j] = INF;
}else{
map[i][j] = INF;
path[i][j] = INF;
}
}
}
for(int i = 0 ; i < m ; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
map[start][end] = Math.min(map[start][end], cost); // 이미 저장되어 있을 지 모르니까, 최솟값 저장
path[start][end] = start;
}
for(int k =1 ; k < n+1 ; k ++){
for(int i = 1; i < n+1 ; i++){
for(int j = 1 ; j < n+1 ; j++){
if(i!=j && map[i][j] > map[i][k] + map[k][j]){ // 바로 오는 길(map[i][j])보다 경로 k를 거쳐서 오는 길(map[i][k] + map[k][j])이 더 빠를 경우
map[i][j] = map[i][k] + map[k][j]; // 최소 비용 저장
path[i][j] = path[k][j]; // 도착점 j로 가기 전에, 들른 곳(path[k][j]) 저장
}
}
}
}
for(int i = 1 ; i < n +1 ; i++){
for(int j = 1; j < n+1 ; j++){
sb.append(map[i][j]==INF ? 0+" " : map[i][j]+" "); // 최소 비용 출력
}
sb.append("\n");
}
Stack<Integer> stack = new Stack<>();
for(int i = 1 ; i < n+1 ; i++){
for(int j = 1 ; j < n+1 ; j++){
if(path[i][j] == INF) sb.append("0\n"); // 갈 수 없는 경우
else{
int end = j;
stack.push(end);
/*
i->j 경로라고 할 경우,
j전에 들렸던 곳을 계속해서 타고 가서
i를 만날때까지 스택에 넣으며 반복하는 로직
=> 마지막 도착점부터 시작점까지 타고 거꾸로 타고 감
*/
while( i != path[i][end] ){
end = path[i][end];
stack.push(end);
}
stack.push(i); // 마지막인 시작점도 출력해야 하므로!
sb.append(stack.size());
while(!stack.isEmpty()){ // 시작점부터 마지막점까지 출력(stack > FILO)
sb.append(" "+stack.pop());
}
sb.append("\n");
}
}
}
System.out.println(sb.toString());
}
}
Author And Source
이 문제에 관하여([BOJ]11780번 플로이드2 (Java)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dot2__/BOJ11780번-플로이드2-Java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)