[백준_11403번] 경로 찾기

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

11403번: 경로 찾기

[문제]

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

 

[입력 조건]

첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

 

[코드]

import java.util.*;

public class BaekJoon_11403 {
	static int[][] graph;
	static int n;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		graph=new int[n][n];
	
		for(int i=0;i<n;i++) 
			for(int j=0;j<n;j++) 
				graph[i][j]=sc.nextInt();
		
		// 플로이드 워셜 알고리즘
		for(int k=0;k<n;k++) {
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					/*
					 * i에서 j로 가는 길을 다른 정점 k를 거쳐 갈 수 있다면
					 * 두 노드는 연결되어 있는 것이기 때문에 1로 바꿔준다. 
					 */
					if(graph[i][k]==1&&graph[k][j]==1)
						graph[i][j]=1;
				}
			}
		}
		
		StringBuilder sb=new StringBuilder();
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				sb.append(graph[i][j]+" ");
			}
			sb.append("\n");
		}
			
		System.out.println(sb);		
	}

}

 

[고찰]

 이번 문제는 모든 노드로 부터 다른 모든 노드까지 연결되어 있는지 확인해야하기 때문에 다익스트라 알고리즘이 아닌 플로이드 워셜 알고리즘을 사용해야 한다. 3중 for문을 사용하여 구현하는 플로이드 워셜 알고리즘을 사용하여 모든 노드의 연결 유무를 검사하는 방식으로 해결할 수 있다.

 노드 i와 k가 연결되어 있고, k와 j가 연결되어 있다면 두 노드는 연결되어 있기 때문에 값을 1로 바꿔주면 된다. 즉, 노드 i로부터 j까지 다른 정점 k를 거쳐 갈 수 있다면 두 노드는 연결되어 있다고 판단한다.