BOJ) 플로이드 (11404 번)

플로이드

11404번: 플로이드

 

모든 도시의 쌍 (A, B)에 대해서 도시 A -> 도시 B로 가는데 필요한 비용의 최솟값을 구하는 문제다.

사실, 최단거리를 보면 다익스트라를 가장 먼저 떠올렸을 것이다.

플로이드-워셜에 분류되어 있어서 플로이드-워셜 방법으로 접근을 했다.

근데, 다시 생각해보면, 모든 경로를 구해야하기 때문에, 모든 도시의 쌍 (A,B)의 거리를 다익스트라로 구한다고하면, 시간이 더욱 오래 걸릴 것 같다.

모든 도시의 쌍의 최단 거리 정보를 저장해두는 플로이드 워셜이 더 적합하다고 느껴지기는 한다.

 

중간 도시들인 stopOver, 시작점인 start, 도착지인 end의 3중 loop를 순회하면서, 시작점에서 도착지까지의 최솟값을 저장해준다.

이 때, 자기 자신의 도시는 갈 수 없어야해서 조건문을 추가시켰다.

또한, 최솟값을 저장하기 때문에, 현재 저장되어있는 값과, stopOver를 경유해서 도착하는 값의 최솟값으로 최신화 해주었다.

이를 위해서 모든 도시의 값을 MAX_VALUE로 초기화 시켰고, 직접 연결되어있는 도시들은 해당 비용의 최솟값을 미리 저장해서 간단한 플로이드 워셜을 적용할 수 있도록 했다.

 

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Floyd_11404 {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine()), m = Integer.parseInt(br.readLine());
    List<City>[] cities = initCities(n);
    while(m-- >0) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      int left = Integer.parseInt(st.nextToken())-1, right = Integer.parseInt(st.nextToken())-1, cost = Integer.parseInt(st.nextToken());
      cities[left].add(new City(right, cost));
    }

    br.close();
    solution(n, cities);
  }

  private static List<City>[] initCities(int n) {
    List<City>[] cities = new ArrayList[n];
    for(int i=0; i<n; i++) {
      cities[i] = new ArrayList<>();
    }
    return cities;
  }

  private static void solution(int n, List<City>[] cities) {
    int[][] costArr = initCostArr(n, cities);
    setCostArr(n, costArr);
    printCost(costArr);
  }

  private static void printCost(int[][] costArr) {
    final String NEW_LINE = "\n", SPACE = " ";
    final String ZERO = "0";
    StringBuilder sb = new StringBuilder();
    for(int[] costLine : costArr) {
      for(int cost : costLine) {
        sb.append(cost == Integer.MAX_VALUE ? ZERO : cost).append(SPACE);
      }
      sb.append(NEW_LINE);
    }
    System.out.println(sb.toString());
  }

  private static void setCostArr(int n, int[][] costArr) {
    for(int stopOver=0; stopOver<n; stopOver++) {
      for(int start=0; start<n; start++) {
        for(int end=0; end<n; end++) {
          if(start != end && costArr[start][stopOver] != Integer.MAX_VALUE && costArr[stopOver][end] != Integer.MAX_VALUE) {
            costArr[start][end] = Math.min(costArr[start][end], costArr[start][stopOver] + costArr[stopOver][end]);
          }
        }
      }
    }
  }

  private static int[][] initCostArr(int n, List<City>[] cities) {
    int[][] costArr = new int[n][n];
    for(int i=0; i<n; i++) {
      Arrays.fill(costArr[i], Integer.MAX_VALUE);
      for(City city : cities[i]) {
        costArr[i][city.vertex] = Math.min(city.cost, costArr[i][city.vertex]);
      }
    }

    return costArr;
  }

  private static class City {
    int vertex, cost;
    public City(int vertex, int cost) {
      this.vertex = vertex;
      this.cost = cost;
    }
  }
}