문제

문제링크

접근

• 효율성 점수가 따로 있는 문제였지만, 우선 정점의 최대 개수가 200이라는 점에서 완탐이 가장 먼저 떠올랐다.
• 단순히 두 점에 관한 연산이 아니라 세 점 이상의 경우를 고려해야 했기 때문에 플로이드-워샬 알고리즘으로 각 정점끼리의 최소 비용을 구했다.
• 그리고 출발점 기준으로 연결된 모든 정점들에 대해 같이 타고 간다고 가정하며 더 적은 비용을 찾아나갔다.

풀이

import java.util.*;

class Solution {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int[][] graph = new int[n][n];
        int INF = 10000000;
        
        for (int i = 0; i < n; i++) {
            Arrays.fill(graph[i], INF);
            graph[i][i] = 0;
		}
        
        for (int[] fare: fares) {
            int start = fare[0] - 1;
            int end = fare[1] - 1;
            graph[start][end] = fare[2];
            graph[end][start] = fare[2];
        }
        
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
                }
            }
        }
        
        int answer = graph[s-1][a-1] + graph[s-1][b-1];
        for (int i = 0; i < n; i++) {
            if (i != s-1 && graph[s-1][i] != INF && graph[a-1][i] != INF && graph[b-1][i] != INF) {
                answer = Math.min(answer, graph[s-1][i] + graph[i][b-1] + graph[i][a-1]);
            }
        }
        
        return answer;
    }
}