BOJ- 11404 ) 플로이드

개발자가될수있을까? 2020. 2. 17. 23:03

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

플로이드-워셜문제의 기본적인 형태이다.

그래프에서 전체의 최단경로를 구할때에 O(N^3)으로 구할수있다.

For문을 돌면서 나와 인접하게 갈수있는 경로를 갱신하면서 최단경로를 구하는 알고리즘이다.

약간 외워서 푸는꼴.. 3중 for에 mid start end 순으로 들어가서 거쳐서 건너간다 라는 식으로 생각하면 쉽다.

import java.util.Scanner;

public class Main {
	static int num;
	static int INF = 2147000000;
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		num = scan.nextInt();
		int graph[][] = new int[num+1][num+1];
		int bus = scan.nextInt();

		for(int y = 1 ; y <= num ; y++) {
			for(int x = 1 ; x <= num ; x++) {
				graph[y][x] = INF;
				if(y==x) graph[y][x] = 0;
			}
		}
	
		for(int index = 0 ; index < bus; index++) {
			int start , end  , cost ;
			start = scan.nextInt();
			end = scan.nextInt();
			cost = scan.nextInt();
			if(graph[start][end] > cost) graph[start][end] = cost;
			
		}
		
		
	
		
		for(int mid = 1;  mid<= num ;  mid++) {
			for(int start = 1 ; start <= num ; start++) {
				for(int end = 1 ; end <= num ; end ++) {
					if(graph[end][mid] != INF && graph[mid][start] != INF) {
						if(graph[end][start] > graph[end][mid] + graph[mid][start]){
							graph[end][start] = graph[end][mid] + graph[mid][start];
						}
					}
				}
			}
		}
		for(int y = 1 ; y <= num ; y++) {
			for(int x = 1 ; x <= num ; x++) {
				if(graph[y][x] == INF) System.out.print(0+" ");
				else System.out.print(graph[y][x]+ " ");
			}
			System.out.println();
		}
		
	}

}