문제 : 경로찾기

문제링크
실버 1
그래프 탐색 플로이드-와샬

그래프 G
모든 정점 (i,j)에 대해서 i->j로 가는 경로가 있는지 없는지 구하기

입력

정점의 수 N
인접행렬 (N줄)

출력

인접행렬로 i,j 1,0으로 표현

풀이

플로이드-와샬

모든 정점에서 모든 정점으로 최단 경로를 구할 때
블로그 참고
이런 알고리즘이 있었다니! 거쳐가는 좌표인 k를 추가해서 a->k 이고 k->b이면 a->b라는 삼단논법(?)같은 알고리즘이다. 가중치가 달라진다면 dp개념이 들어가서 이해하기 조금 어려운것 같지만 지나가는 점 k에대한 i,j에 대한 최소값을 갱신해나가다보면 자동으로 완성이되게된다. 가중치가 같으면 아주 이해하기 쉬운 알고리즘이다.

코드

import java.util.Scanner;

public class 백준11403 {
	static int N,cnt=0;
	static Scanner scan =new Scanner(System.in);
	static StringBuilder sb=new StringBuilder();
	static int[][] arr,arr2;
	static boolean[][] visited;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int N=scan.nextInt();
		arr=new int[N+1][N+1];

		for(int i=1;i<=N;i++) {
			for(int j=1;j<=N;j++) {				
				arr[i][j]=scan.nextInt();
			}
		}
		for(int k=1;k<=N;k++) {// 거쳐가는 노드
			for(int i=1;i<=N;i++) {
				for(int j=1;j<=N;j++) {
					if(arr[i][k]==1&&arr[k][j]==1) {
						arr[i][j]=1;
					}
				}
			}
		}
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=N;j++) {
				sb.append(arr[i][j]+" ");
			}
			sb.append("\n");
		}
	
		System.out.print(sb);
	}

}