[플로이드 워셜] 경로 찾기(백준 11403번, 자바)

 

https://www.acmicpc.net/problem/11403

11403번: 경로 찾기

 

가중치 없는 방향 그래프 

[입력] 인접행렬

[출력] 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력

 

v 플로이드 워셜  

그래프에서 가능한 모든 노드쌍에 대한 최단 거리를 구하는 알고리즘 

 for(int k=0;k<N;k++) {
	for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				map[i][j]=Math.min(map[i][j], map[i][k]+map[k][j]);
			}
	}
}

 

다익스트라

하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int[][] map;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		 int N = Integer.parseInt(br.readLine());

		 map=new int[N][N]; //인접행렬
		 
		 for(int i=0;i<N;i++) {
			 StringTokenizer st=new StringTokenizer(br.readLine());
			 for(int j=0;j<N;j++) {
				 map[i][j]=Integer.parseInt(st.nextToken());
			 }
		 }
		 
		 for(int k=0;k<N;k++) {
			 for(int i=0;i<N;i++) {
				 for(int j=0;j<N;j++) {
					if(map[i][k]==1 && map[k][j]==1) { //i->k -> j로 가는 경로가 존재한다면
						map[i][j]=1;
					}
				 }
			 }
			
		 }
		 
		 for(int[] i: map) {
			 for(int j:i)
				 System.out.print(j+" ");
			 System.out.println();
		 }
		 
	}
}