[ 백준 11404 ] 플로이드

1. 문제 링크 https://www.acmicpc.net/problem/11404

11404번: 플로이드

 

2. 문제 

3. 문제 요약

N개의 노드와 M개의 엣지를 가지는 Directed 그래프에서

각 점에서 다른 점들로 가는 경로의 최소 비용을 찾는 문제이다. 

 

 

4. 문제 풀이

(1) 배열 선언 
 N개의 노드를 갖는, Directed 그래프이므로, 2차원 배열의 열을 [source] 목적지를 [target] 배열로 두고

 각각의 배열을 선언했다.

 

(2) 갱신

  각각의 노드로부터 정해진 비용으로 모든 노드를 탐색하기 위해, 각각의 노드별 트리를 생각했다.

  최초로 주어진 엣지들의 비용을 이용해서 다음과 같은 경우에, 갱신하도록 알고리즘을 구현했다.
    (a) 직접경로가 비어있지만, 우회경로가 있거나
    (b) 직접경로가 있지만, 우회경로의 비용이 더 낮을 때

 

(3) O(N^3) !! 
   이를 알고리즘으로 구현하고 보니,

   N개의 출발 노드로부터, (N-1)개의 목적 노드에 대한 갱신을
   최대 (N-1)번 반복을 하는 알고리즘이 되었다. (최악의 경우 ~ 최단경로가 경사트리) 

  즉,  [Source] 노드에서 [Current] 노드를 거쳐 [Target] 노드로의 최단거리를 구하도록 구현했다.

  

 

(3) O(N^3) !! 

  O(N^3)이 등장하게 되어 무척 당황했다.

  보통 10^8 이내의 연산을 선호하는데,  N이 100 이하의 자연수이므로 가능은 하지만 찝찝한 느낌

 

  O(N^2)으로 가능한 방법을 계속해서 고민하다 O(N^3)으로 구현을 한 뒤,

 불필요한 연산들을 제거해서, 최대한 효율적으로 동작하도록 세부적인 성능개선에 집중했다.

 

5. 풀이 코드

public static void problem11404() throws Exception {
    N = Integer.parseInt(br.readLine());
    M = Integer.parseInt(br.readLine());
    min = new int[N][N];
    for (int i = 0; i < M; i++) {
        str = new StringTokenizer(br.readLine());
        int src = Integer.parseInt(str.nextToken()) - 1;
        int tgt = Integer.parseInt(str.nextToken()) - 1;
        int cost = Integer.parseInt(str.nextToken());         
        if( min[src][tgt] == 0 || min[src][tgt] > cost)
            min[src][tgt] = cost;
    }
    search();
    print2d(min);
    bw.flush();
}

 

public static void search() {
    for (int cur = 0; cur < N; cur++) {
        for (int src = 0; src < N; src++) {
            if (min[src][cur] == 0)    continue;
            for (int tgt = 0; tgt < N; tgt++) {
                if ( (tgt-src)*(tgt-cur)==0 || min[cur][tgt] == 0) continue;
                int cost = min[src][cur] + min[cur][tgt];
                if (min[src][tgt] > cost || min[src][tgt] == 0)
                    min[src][tgt] = cost;
            }
        }
    }
}