[프로그래머스] 택시 합승 요금

총 노드의 개수는 200개 , 간선은 n*(n-1)/2 이다.

이 문제는 중간지점 X 를 거쳐 가거나 or 거쳐가지 않거나 의 두 경우이다.

• 중간지점을 거쳐가지 않는 경우
  • sa + sb
• 중간지점을 거쳐가는 경우
  • sx + xa + xb

이다.

처음에는 디익스트라인 줄 알았는데, 디익스트라는 “한 점” 으로부터 “모든 노드까지의 최단 거리” 이다.

하지만 우리는 현재 x 가 어느지점이 될 지도 모르는 상황에서 디익스트라로 풀려면 결국 모든 지점으로부터의 디익스트라를 하는 형태? 가 될 것 같았다.

따라서 모든노드 → 모든 노드까지의 최단거리를 구하는 플로이드 워셜을 고려했다.

플로이드 워셜은 O(n^3) 의 시간복잡도를 갖는다.

짧게 복기 해 보자면

• nx n 의 거리 테이블을 두고
• 모든 간선 들을 사용해, 두 노드 사이 거리가 주어진 것들은 모두 초기화
  • 자기 → 자기 = 0 으로 두고
  • 나머지는 INF 값으로 초기화
• 모든 노드들을 iterate 하면서, 현재 노드를 거쳐가는 경우가 “두 노드”의 최단 거리보다 짧은 경우에 대해 업데이트

n 이 200이기에 충분히 가능한 문제였다.

이 문제는 플로이드 워셜을 통해 모든 노드로부터 모든 노드로까지의 최단거리를 업데이트 해 둔 후

• 각 x 에 대해
  • min 과 sa + sb 중 최소를 min으로 업데이트
  • min 과 와 sx + xa + xb 중 최소 값을 min 으로 업데이트 해야 한다.
• 나는 평소 INF 로서 그냥 Integer.MAX_VALUE 를 사용해왔었는데, 이 경우 연산이 들어가서 스택오버플로우가 일어나 예상하지 못한 결과가 나올 것 같았다.
• 따라서 이 문제는 INF 값을 대충..? 예상해보자면 노드의 개수는 200개고, 각 fee 의 최대가 10만 이기에, 두 노드 198개의 노드를 타고 가야 하더라도 그 총합은 2000만 정도로 허용 가능했다.
• INF = 2천만으로 설정하고 풀이했다

import java.util.*;
class Solution {
    private static final int INF = 200_000_00;
    // n : 노드 개수
    // s : 시작점
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int[][] table = init(fares, n);
        floyd(table, n);

        int min = Integer.MAX_VALUE;
        for(int x = 0; x < n; x++) {
            int na = a-1; int nb = b-1; int ns = s-1;
            // sa + sb 구해 두고, sx + xa + xb 중 최소가 되는 것 구하기
            int temp = Math.min(
                table[ns][na] + table[ns][nb],
                table[ns][x] + table[na][x] + table[nb][x]);
            min = Math.min(temp, min);
        }

        return min;
    }

    // 각 노드들 사이의 최대 경로를 구하여 세팅한다
    private void floyd(int[][] table, int n) {
        for(int c = 0; c < n; c++) {
            // 모든 ij 에 대해 ic + jc 가 ij
            for (int i = 0; i < n; i++) {
                if(c == i) continue;
                for (int j = 0; j < n; j++) {
                    if( i == j || c == j) continue;
                    if(table[i][j] > table[i][c] + table[j][c]) {
                        table[i][j]  = table[i][c] + table[j][c];
                        table[j][i]  = table[i][c] + table[j][c];
                    }
                }
            }
        }
    }

    private int[][] init(int[][] fares, int n) {
        int[][] table = new int[n][n];

        for(int[] f : fares) {
            // f[0] 과 f[1] 사이의 비용 f[2]
            table[f[0]-1][f[1]-1] = f[2];
            table[f[1]-1][f[0]-1] = f[2];
        }

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(i == j) table[i][j] = 0;
                else if(table[i][j] == 0) table[i][j] = INF;
            }
        }

        return table;
    }

}