11403번 - 경로 찾기

1️⃣ Floyd-Warshall

 

✏️ 풀이 과정

문제를 이해하는 게 조금 난해할 수 있는데 유향 그래프가 주어질 때 어떤 경로를 거쳐서라도 특정 점에서 특정 점으로 갈 수 있는지 여부를 표시하라는 뜻입니다. 가령 예제 1의 경우 그래프가 사이클이기 때문에 어떤 점에서도 다른 모든 점으로 갈 수 있습니다.(자기 자신으로도요) 그래서 모든 원소가 1이 됩니다.

 

문제를 해결하기 위해 DFS를 모든 정점마다 돈다고 생각하면 굉장히 중복이 많아집니다. 대신 플로이드-워셜 알고리즘을 응용하면 좀 더 간단하고 빠르게 문제를 해결할 수 있습니다. 원래 해당 알고리즘은 최단 거리를 계산하는 알고리즘이지만 문제에서는 연결되어 있는지의 여부만이 관심사이므로 좀 더 코드를 간단하게 만들 수 있습니다.

 

3중 for문에서 중계지점이 가장 바깥에 있고 중간이 시작점, 가장 안쪽이 끝점입니다. 이 때 시작점에서 중계점으로 가는 길이 있고 중계점에서 끝점으로 가는 길이 있으면 인접 행렬에 1로 표시해주면 됩니다. 기존 거리 계산과 같은 원리로 작동하기 때문에 모든 정점에 대해 연결 여부를 구할 수 있습니다. 알고리즘을 돌리고 인접행렬을 출력하면 문제가 해결됩니다.

 

💻 코드

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

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[][] adjMat = new int[N][N];
		StringTokenizer st;
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<N;j++) {
				adjMat[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(adjMat[i][k] == 1 && adjMat[k][j] == 1) {
						adjMat[i][j] = 1;
					}
				}
			}
		}
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				System.out.print(adjMat[i][j]+" ");
			}
			System.out.println();
		}
		br.close();
	}
}