[백준] 11403번 - 경로 찾기

 

11403번: 경로 찾기

 

 

 

 

 

플로이드 워셜(Floyd - Warshall) 알고리즘에 대한 기본 개념을 이해할 수 있는 문제이다. 이전에 학습한 다익스트라 알고리즘이 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이었다면, 플로이드 - 워셜 알고리즘은 모든 정점에서 다른 모든 정점까지의 최단 거리를 구하고자 할 때 사용하는 알고리즘이다. 

 

플로이드 워셜 알고리즘의 작동 방법은 다이나믹 프로그래밍을 적용한 완전 탐색 방법으로, 정점의 갯수가 N 일 때 시간 복잡도 O(N^3)을 갖는다. 따라서 N의 크기가 너무 크다면 사용하기 곤란하며 N^3이 허용할 수 있는 범위 내의 사이즈라면 사용해도 좋다.

 

플로이드 워셜 알고리즘의 기본 코드는 삼중 반복문을 사용하며 아래와 같다.

 

// INF는 두 정점이 서로 도달할 수 없다는 것을 의미한다. 편의상 Integer의 최대값을 넣었지만 상황에 따라 허용하는 최대값 + 1 을 넣어도 된다. 
final int INF = Integer.MAX.VALUE;

// 정점의 갯수
int N = 100;


// 정점간의 간선 가중치 정보
int[][] arr = new arr[N+1][N+1];

for (int i = 1; i <= N; i++) {
    //arr을 INF으로 초기화
    Arrays.fill(arr[i], INF);
    // 보통은 하나의 정점 i 에 대해서 i - i 연결되어 있다고 간주하지는 않으므로 arr[i][i]을 0으로 초기화
    arr[i][i] = 0;
}

// 그래프에서 서로 연결되어 있는 두 정점 a, b의 간선 가중치 c를 arr[a][b] = c; 으로 담는다.
// 방향이 있는 그래프가 아니라면 arr[b][a] = c; 을 추가


// 가능한 모든 간선 후보에 대한 탐색을 한다. 
for (int k = 1; k <= N; k++) {
	for (int i = 1; i <= N; i++) {
    	for (int j = 1; j <= N; j++) {
        	// 만약 i가 k를 거쳐서 j에 도달할 수 있다면 두 정점은 연결되어 있다.
        	if (arr[i][k] != INF && arr[k][j] != INF) 
            	// 이전에 기록된 i -> j 경로의 비용과 현재 탐색 중인 i -> k -> j을 비교하여 더 작은 값으로 갱신 
            	arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[k][j]);
        }
    }
}

 

위와 같이 주어진 그래프에서 두 정점간의 간선이 될 수 있는 모든 경우의 수에 대하여 연결되어 있는지 판단하여 두 정점이 연결되어 있다면 기존의 비용과 비교하여 arr[i][j]을 갱신한다.

 

이번 문제에서는 최단 경로가 아닌 모든 정점에 대한 연결여부만 확인하면 되기 때문에 i 에서 k를 거쳐 j로 가는 경로가 존재한다면 arr[i][j] = 1 으로 값만 넣어주면 된다. 

 

 

 

 

 

 

 

 

 

import java.util.*;
import java.io.*;

public class Main {
	
	
    public static void main (String[] args) throws IOException {
        
    	
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = {};
        
        
        int N = Integer.parseInt(br.readLine());
        
        
        int[][] path = new int[N+1][N+1];

        for (int i = 1; i <= N; i++) {
            input = br.readLine().split(" ");
            for (int j = 1; j <= N; j++) {
            	// 두 정점에 간선이 존재하면 1, 간선이 존재하지 않으면 0이 들어간다.
                path[i][j] = Integer.parseInt(input[j-1]);
            }
        }
        
        
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                	// 정점 i에서 출발하여 정점 k를 거쳐 정점 j에 도달할 수 있다면 정점 i와 j는 서로 연결되어 있다.
                    if (path[i][k] == 1 && path[k][j] == 1) 
                        path[i][j] = 1;
                }
            }
        }
        
        
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) 
                sb.append(path[i][j] + " ");
            sb.append("\n");
        }
        
        System.out.println(sb);
        
        
        br.close();
    }
}