2. 알고리즘사이트/1. 백준

플로이드 [백준 11404][JAVA][골드 4][플로이드 와샬][floydWarshall]

isaacToast 2020. 4. 11. 14:53
반응형

 

[광고 누르면 오늘의 행운 상승!!]

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

 

11404번: 플로이드

첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다. 시작

www.acmicpc.net

플로이드 와샬 문제

2차원 배열을 이용해서 i -> j 도시로 가는 최소 비용을 구한다.

i-i 나 j-j 의 경우 0을 출력한다.

i : 출발지
j : 도착지
k : 경유지 

일때, i -> k + k -> j 와 i -> j 중 작은 값이 i -> j까지의 최소 거리이다.

package Study3;

import java.io.*;
import java.util.*;
 
public class 플로이드 {
    public static int city;
    public static int[][] dis;
    public static final int INF = 1000000000;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        city = Integer.parseInt(br.readLine());
        int bus = Integer.parseInt(br.readLine());
        
        dis = new int[city][city];
        
        for(int i=0; i < city; i++) {
            for(int j=0; j < city; j++) {
                if(i == j) continue;
                dis[i][j] = INF;
            }
        }
        
        while(bus-- > 0) {
            st = new StringTokenizer(br.readLine());
            
            int A = Integer.parseInt(st.nextToken())-1;
            int B = Integer.parseInt(st.nextToken())-1;
            int D = Integer.parseInt(st.nextToken());
            
            dis[A][B] = Math.min(dis[A][B], D);    
        }
 
        floydWarshall();

        StringBuilder sb = new StringBuilder();
        for(int i=0; i < city; i++) {
            for(int j=0; j < city; j++) {
                if(dis[i][j] >= INF) sb.append("0 ");
                else sb.append(dis[i][j] + " ");
            }
            sb.append("\n");
        }
        
        System.out.println(sb.toString());
    }
    
    public static void floydWarshall() {
        // 경유노드 
        for(int k = 0; k < city; k++) {
            // 출발노드
            for(int i =0 ; i < city; i++) {
                // 도착노드
                for(int j = 0; j < city; j++) {
                    //i에서 k를 거쳤다가 k에서 j 까지 가는 거리와 i에서 j 까지 가는 거리를 비교해서 작은 값이 최소거리이다.
                    dis[i][j] = Math.min(dis[i][k] + dis[k][j], dis[i][j]);
                }
            }
        }
    }
}
반응형