반응형
이 문제는 플로이드-워셜 알고리즘을 푸는 문제입니다.
문제를 풀 때 주의해야하는 점은 시작 도시와 도착 도시를 연결하는 노선이 하나가 아닐 수 있다는 것입니다.
노선을 입력받아서 그 비용이 더 적은지를 비교한 후에 넣어야합니다.
플로이드 워셜 알고리즘은 각 정점으로부터 다른 정점까지 갈 때 거쳐가는 정점을 추가하면서 진행하는 알고리즘입니다.
코드를 보며 추가로 설명드리겠습니다.
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));
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
int[][] map = new int[n+1][n+1];
for(int i =0; i<=n; i++){
for(int j = 0; j<=n; j++){
if(i == j)
map[i][j] = 0;
else
map[i][j] = 100_000*n;
}
}
for(int i = 0; i<m; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
map[a][b] = Math.min(map[a][b], c);
}
// 거쳐가는 지점
for(int i = 1; i<=n; i++)
//시작지점
for(int j = 1; j<=n; j++)
//도착지점
for(int k = 1; k<=n; k++)
map[j][k] = Math.min(map[j][k], map[j][i] + map[i][k]);
for(int i = 1; i<=n; i++){
for(int j = 1; j<=n; j++) {
if(map[i][j] == 100_000*n)
System.out.print(0+" ");
else
System.out.print(map[i][j] + " ");
}
System.out.println();
}
}
}
이 문제에서는 for문 안의 시작 지점이 j이고 도착 지점이 k일 때 i를 거쳐서 가면 더 비용이 적은가를 비교하는 문제입니다.
반응형
댓글