Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

25. 최단 경로

그래프의 간선에 가중치가 없으면 BFS로 최단거리를 찾을 수 있습니다. 가중치가 있다면 어떨까요?

Java / Python

5. 플로이드

11404번

플로이드 와셜 알고리즘을 배우는 문제

이번 문제는 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하는 문제입니다.
플로이드 와샬 알고리즘을 사용합니다!

• Java

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

public class Main {
	static final int INF = 1000000000;
	static int[][] dist; 
	static int cityCnt;
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));   
		StringTokenizer st = null;
        
		cityCnt = Integer.parseInt(br.readLine());			
		int busCnt = Integer.parseInt(br.readLine());
        
		dist = new int[cityCnt + 1][cityCnt + 1];

		for(int i = 1; i <= cityCnt; i++){
			for(int j = 1; j <= cityCnt; j++){
				if(i != j) dist[i][j] = INF;
			}
		}
        
		while(busCnt-- > 0){    
			// 입력값 초기화
			st = new StringTokenizer(br.readLine()); 
            
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());			
			int time = Integer.parseInt(st.nextToken());
            
			dist[start][end] = Math.min(dist[start][end], time);
		}
		floydWarshall();
        
		StringBuilder sb = new StringBuilder();
		for(int i=1; i <= cityCnt; i++) {
			for(int j=1; j <= cityCnt; j++) {
				if(dist[i][j] >= INF) sb.append("0 ");
				else sb.append(dist[i][j] + " ");
			}
			sb.append("\n");
		}
        
		bw.write(sb.toString());
        
		bw.flush();
		bw.close();
		br.close();
	}

	public static void floydWarshall() { 
		// 기준 K
		for(int k = 1; k <= cityCnt; k++) {
			// 출발 노드 i
			for(int i = 1; i <= cityCnt; i++) {
				// 도착 노드 j
				for(int j = 1; j <= cityCnt; j++) {
					//i -> k , k -> j 가는 거리, i -> j 가는 거리를 비교 (작은 값 : 최소거리)
					dist[i][j] = Math.min(dist[i][k] + dist[k][j], dist[i][j]);
				}
			}
		}
	}
}

• Python

import sys
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
INF = 10000000000
city = [[INF] * N for i in range(N)]

for i in range(M):
    a, b, c = map(int, sys.stdin.readline().split())
    if city[a - 1][b - 1] > c:
        city[a - 1][b - 1] = c
for k in range(N):
    for i in range(N):
        for j in range(N):
            if i != j and city[i][j] > city[i][k] + city[k][j]:
                city[i][j] = city[i][k] + city[k][j]
for i in city:
    for j in i:
        if j == INF:
            print(0, end=' ')
        else:
            print(j, end=' ')
    print()