[BOJ] 플로이드 워셜

플로이드 워셜이란 그래프 최단 경로를 구하는 알고리즘 중 하나로, 모든 정점에서 모든 정점까지 최단 거리를 구하는 알고리즘이다. 플로이드 워셜 알고리즘의 점화식은 다음과 같다.

 

다익스트라 알고리즘과 비슷해보이지만, 소스코드가 다익스트라에 비해 짧고 구현이 쉽다. 

 

다익스트라 알고리즘

1. 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다.
2. 1차원 리스트에 저장한다.

 

플로이드-워셜 알고리즘

1. 모든 지점에서 다른 모든 지점까지의 최단 거리를 저장한다.
2. 2차원 테이블에 저장한다.

for (int k = 0; k < n; k++) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (graph[i][k] == 1 && graph[k][j] == 1) {
        graph[i][j] = 1;
      }
    }
  }
}

 

 

[ BOJ 11403 ] 경로 찾기

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

 

처음에는 그래프 인접 리스트로 만들어 풀이를 하였으나 간과한 부분이 있었다.

 

1. 경로 탐색

i → k와  k → j 일 경우, i → j 가 존재하는 것을 단순히 인접 리스트로는 확인할 수 없기에 경로 탐색 로직이 필요하다.

 

2. 자기 자신 경로 설정

첫 번째 예제 입출력만 보고 자기 자신으로의 경로를 항상 1로 간주하고 풀이했었다. 그러나 두 번째 예제 입출력을 봤을땐 1로 간주하지 않고 있으며, 자기 자신으로의 경로에는 두 가지 상황이 존재한다.

1. 입력에서 주어지는 경우
2. 경로 탐색에서 새로 추가되는 경우

예제 입력 2

7
0 0 0 1 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 1 1 0
1 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 1 0 0 0 0

 

예제 출력 2

1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 0 0 0 0 0
1 0 1 1 1 1 1
1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 1 0 0 0 0

 

문제의 입력에서 명시적으로 0으로 주어질 경우, 경로 탐색을 통해 1로 추가되어야 하는 것이다. 따라서 해당 문제에는 플로이드-워셜 또는 DFS/BFS 알고리즘이 필요하다.

 

플로이드-워셜 풀이

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

public class Main {
  static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
  public static void main(String [] args) throws IOException{
    int n = Integer.parseInt(br.readLine());
    int[][] graph = new int[n][n];
    
    for(int i = 0; i < n; i++){
      graph[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }

    for (int k = 0; k < n; k++) {
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
          if (graph[i][k] == 1 && graph[k][j] == 1) {
            graph[i][j] = 1;
          }
        }
      }
    }

    StringBuffer sb = new StringBuffer();
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
        sb.append(graph[i][j]).append(" ");  
      }
      sb.append("\n");
    }

    System.out.println(sb.toString());
  }
};

 

 

 

다음은 플로이드-워셜 알고리즘 관련 백준 문제이다.

 

[BOJ] 케빈 베이컨의 6단계 법칙

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