[백준 코딩테스트] 11403번 경로 찾기

내 풀이

처음에는 유니온-파인드 알고리즘을 사용해 문제를 풀어가려고 하였으나 자꾸 어딘가 막혀서 문제가 풀리지 않았다. 그래서 결국 혼자 힘으로 문제를 풀이 하는 것이 아닌 다른 사람의 풀이를 참고하여 문제를 풀었다.
이 문제는 플로이드 워셜 알고리즘을 사용해 문제를 풀어야 했다. 다익스트라 알고리즘은 들어봤어도 플로이드 워셜 알고리즘은 처음 들어봤기에 바로 코드를 짜는 것이 아닌 알고리즘 공부를 통해 경로를 찾는 과정을 이해했어야 했다.

플로이드 워셜 알고리즘 ?

플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 구하는 알고리즘이다.
다익스트라의 경우 단계마다 최단 경로를 갱신하지만 플로이드 워셜 알고리즘은 거쳐가는 노드를 기준으로 알고리즘을 수행한다.
이때 매 단계마다 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다.

• 플로이드 워셜은 2차원 테이블에 최단 거리 정보 저장
• 동적 계획법을 기반으로 작동
• dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])

위의 점화식의 경우 거쳐가는 노드를 K라고 할 수 있다.

알고리즘	특징	시간 복잡도
플로이드 워셜	모든 정점 쌍의 최단 경로	O(N^3)
다익스트라	단일 출발점에서 다른 정점까지의 최단 경로	O((V+E)log V)

내 코드

자바 코드

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

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        int[][] graph = new int[n][n];
        int[][] answer = new int[n][n];
        
        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++){
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // Floyd-Warshall
        for(int k=0; k<n; k++){
            for(int i=0; i<n; i++){
                if(graph[i][k] == 0) continue;
                answer[i][k] = 1;
                for(int j=0; j<n; j++){
                    if(graph[k][j] == 0) continue;
                    graph[i][j] = 1;
                    answer[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);
    }
}

파이썬 코드

def solve():
   n = int(input())
   graph = [list(map(int, input().split())) for _ in range(n)]
  
   for k in range(n):
       for i in range(n):
           if graph[i][k] == 0 :
               continue
           for j in range(n):
               if graph[k][j] == 0:
                   continue;
               graph[i][j] = 1
  
   for row in graph :
       print(*row)
  
  if __name__ == "__main__":
       solve()def solve():
   n = int(input())
   graph = [list(map(int, input().split())) for _ in range(n)]
  
   for k in range(n):
       for i in range(n):
           if graph[i][k] == 0 :
               continue
           for j in range(n):
               if graph[k][j] == 0:
                   continue;
               graph[i][j] = 1
  
   for row in graph :
       print(*row)
  
  if __name__ == "__main__":
       solve()

참고
https://velog.io/@kimdukbae/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Floyd-Warshall-Algorithm