[ 백준 - 11404 ] 플로이드

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

 

플로이드 워셜(Floyd-Warshall) 알고리즘을 접하게 되어서 알고리즘 연습을 위해서 찾다가 풀게된 문제다.

예전에 문제를 풀 때 다익스트라 알고리즘은 음의 가중치를 해결하지 못해서 고민하다가 이름만 기억하고 있다가 기회가 왔을 때 문제로 연습 하였다.

---

[ 📌 풀이 ]

• 그래프 구성
  • 다른 그래프 문제와 동일하게 출발 -> 도착 (비용) 을 기록할 수 있도록 구성한다.
• 플로이드 워셜 알고리즘
  • 경유 노드를 정해서 다른 노드가 지나가면서 INF 로 설정했던 경로를 도달할 수 있는지 체크한다.
  • V^3 시간 복잡도를 갖고, V^2 의 공간 복잡도를 갖기 때문에 불필요한 연산을 최소로 한다.
• 출력 값 포맷 맞춰주기
  • 문제에서 요구하는 출력 방식을 맞춰준다. (문제 잘 읽을 것)

---

[ 📌 코드 - Python ]

import sys
inp = sys.stdin.readline

N = int(inp())
M = int(inp())
INF = 10000000

graph = [[INF for _ in range(N)] for _ in range(N)]

for idx in range(N):
  graph[idx][idx] = 0

for _ in range(M):
  srt, end, cost = map(int, inp().split())
  srt -= 1
  end -= 1

  graph[srt][end] = min(cost, graph[srt][end])

for mid in range(N):
  for srt in range(N):
    for end in range(N):
      graph[srt][end] = min(graph[srt][end], graph[srt][mid] + graph[mid][end])

for srt in graph:
  for end in srt:
    print(0 if end == INF else end, end=' ')
  print()

 

[ 📌 코드 - Java ]

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));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        int[][] graph = new int[N][N];
        final int INF = 10_000_000;

        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(i == j) {
                    graph[i][j] = 0;
                } else {
                    graph[i][j] = INF;
                }
            }
        }

        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int from = Integer.parseInt(st.nextToken()) - 1;
            int to = Integer.parseInt(st.nextToken()) - 1;
            int cost = Integer.parseInt(st.nextToken());

            graph[from][to] = Math.min(cost, graph[from][to]);
        }

        for(int mid = 0; mid < N; mid++) {  // 중간 경유 노드
            for(int srt = 0; srt < N; srt++) {  // 출발 노드
                for(int end = 0; end < N; end++) {  // 도착 노드
                    int stopoevr = graph[srt][mid] + graph[mid][end];

                    graph[srt][end] = Math.min(graph[srt][end], stopoevr);
                }
            }
        }

        for (int[] srtNodeInfo : graph) {
            for(int endNode : srtNodeInfo) {
                sb.append(endNode == INF ? 0 : endNode).append(' ');
            }
            sb.append(System.lineSeparator());
        }

        System.out.println(sb);
    }
}

---

[ 📌 결과  ]

[ Result ]