[백준 11403번/JAVA] 경로 찾기 (문제 풀이, 코드)

경로 찾기

[문제]

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

 

[풀이]

모든 정점에 대한 경로를 구할때 사용하는 알고리즘은 플로이드-와샬 알고리즘이다.

그냥 0번 정점부터 끝까지 반복문 3개를 돌리게 되는데, 내가 제일먼저 잡은 점이 거치는 정점(k), 두번째가 시작 정점(i), 세번째가 도착 정점(j)이다.

i->k->j가 i->j보다 빠르면 i->k->j로 상태를 업데이트 하면 된다.

 

[코드]

package p;

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

// 플로이드-와샬
public class findRoute_11403 {
	public static void main(String args[]) throws IOException{
		/* input 받기 */
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		int adj[][] = new int[N][N];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine()," ");
			for(int j=0; j<N; j++)
				adj[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(adj[i][j] == 1) continue;
					else if (adj[i][k] == 1 && adj[k][j] == 1) adj[i][j] = 1;
				}
			}
		}
		
		/* output */
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++)
				System.out.print(adj[i][j]+" ");
			System.out.println();
		}
	}
}

[]

내용

GitHub에 티스토리에 올리지 않은 코드들도 업로드 되어 있습니다.