[BAEKJOON] 11404 플로이드

문제 요약

• 알고리즘 분류: 플로이드 워셜
• 난이도: Gold4
• 문제내용:
  • 각 노드간의 최단 거리를 구해라
    • 시작과 도착점은 같은 거리는 없다.
    • 시작점에서 도착점까지 갈수 없으면 0으로 표시한다.

• 사이트: https://www.acmicpc.net/problem/11404

11404번: 플로이드

문제풀이

   이번에는 문제 유형은 그래프 탐색 관련 문제이다.  모든 노드간의 최단 거리를 구하라는 문제가 나와있고 데이터가 최대 100으로 봤을때 플로이드 워셜 알고리즘으로 해결 할 수가 있다. 시간복잡도는 O(N^3)이지만 구현이 간단하다. 플로이드 워셜 알고리즘에 대한 자세한 설명은 여기에서 확인해보면된다.

 플로이드 워셜 알고리즘을 알면 구현 하는데 문제는 없지만 초기값 세팅을 10만 위로 설정해야 하고 플로이드 워셜 알고리즘 구현후 초기값이랑 같은 값은 0으로 변경하는 처리만 잘하면 통과가 될것이다. 접근, 구현 방법에 대한 설명은 알고리즘만 알고 초기값과 후 처리만 하면 끝이기 때문이다.

 Code

Python

import sys
input = sys.stdin.readline

n = int(input())
INF = 1e7
adj = [[INF] * (n + 1) for _ in range(n + 1)]
for _ in range(int(input())):
    a, b, c= map(int, input().split())
    adj[a][b] = min(adj[a][b], c)

for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if(i != j):
                adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])
            else: adj[i][j] = 0

for i in adj[1:]:
    for j in i[1:]:
        print((j, 0)[j == INF], end= ' ')
    print()

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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 M = Integer.parseInt(br.readLine());
		int[][] adj = new int[N + 1][N + 1];
		int INF = Integer.MAX_VALUE / 2;
		for (int i = 1; i <= N; i++) {
			Arrays.setAll(adj[i], x ->  INF);
		}
		StringTokenizer st;
		int a, b, c;
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			adj[a][b] = Math.min(adj[a][b], c);
		}
		for(int k = 1; k <= N; k++) {
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= N; j++) {
					if(i == j) adj[i][j] = 0;
					else adj[i][j] = Math.min(adj[i][j], adj[i][k] + adj[k][j]);
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				sb.append(adj[i][j] == INF? 0 : adj[i][j]).append(" ");
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}

}