문제 해설

이 문제는 a는 S에서 출발하여 A까지 가야하고, b는 S에서 출발하여 B까지 도착해야 한다. 그리고 만약 같이 합승한다면 돈은 한번만 내도 된다.
처음에는 진짜 너무 복잡하게 생각했었는데, S->A로 가는 모든 경로를 구하고 S->B로 가는 모든 경로를 구한다음.. 서로 조합을 해서 같은 경로를 구하고.. 같으면 비용 안내도 되니까 한번만 계산해서 그 중 최솟값을 구할려고 했다...

이걸 굳이 각각 나누어서 경로를 구할 필요가 없었다. 결국에는 어떤 노드까지는 a와 b가 같이 가고, 그 다음 그 노드에서 a는 A까지, b는 B까지 가면 된다. 만약 x->y로 가는 최소비용을 알고 있으면 쉬워진다. 그럼 1부터 n까지의 노드들을 다 탐색하여 같이 가는 노드를 구한 다음, a,b 따로 가는 비용을 구해주면 된다.

여기서 x->y로 가는 최소비용을 구하는 방법은 2가지이다. 다익스트라를 이용해서 구할 수 있고, 모든 비용을 구해야하기 때문에 플로이드 워셜을 사용해도 된다.

다익스트라를 이용한 방법

플로이드 워셜보다 다익스트라를 먼저 생각한 것은 시간 효율성 때문이다. 다익스트라는 시간복잡도가 O(ElogV)이기 때문에 여기서 n은 200이하의 자연수이기 때문에 O(E)가 나온다. 즉, 간선의 개수와 시간복잡도가 같다. (O(Elog200) -> O(2E) -> O(E))

파이썬

import heapq

def solution(n, s, a, b, fares):
    INF = int(1e9)
    answer = INF

    def dijkstra(start):
        dist = [INF for _ in range(n + 1)]
        dist[start] = 0
        q = []
        heapq.heappush(q, [dist[start], start])
        while q:
            cur_dist, node = heapq.heappop(q)
            for tmp_node, tmp_dist in cost[node]:
                if dist[tmp_node] > cur_dist + tmp_dist:
                    dist[tmp_node] = cur_dist + tmp_dist
                    heapq.heappush(q, [dist[tmp_node], tmp_node])
        return dist

    cost = [[] for _ in range(n + 1)]
    for start, end, val in fares:
        cost[start].append((end, val))
        cost[end].append((start, val))

    dist = []
    for i in range(n + 1):
        dist.append(dijkstra(i))
    # print(dist)
    for i in range(1, n+1):
        answer = min(dist[s][i] + dist[i][a] + dist[i][b], answer)
    return answer

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    class Node implements Comparable<Node> {
        int node;
        int distance;

        public Node(int node, int distance) {
            this.node = node;
            this.distance = distance;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.distance, o.distance);
        }
    }

    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = Integer.MAX_VALUE;

        ArrayList<Node>[] cost = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            cost[i] = new ArrayList<>();
        }

        for (int[] fare : fares) {
            int start = fare[0];
            int end = fare[1];
            int val = fare[2];
            cost[start].add(new Node(end, val));
            cost[end].add(new Node(start, val));
        }

        int[][] dist = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }

        for (int i = 1; i <= n; i++) {
            dijkstra(i, n, cost, dist[i]);
        }

        for (int i = 1; i <= n; i++) {
            answer = Math.min(answer, dist[s][i] + dist[i][a] + dist[i][b]);
        }

        return answer;
    }

    public void dijkstra(int start, int n, ArrayList<Node>[] cost, int[] dist) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        dist[start] = 0;

        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            for (Node next : cost[cur.node]) {
                int newDist = dist[cur.node] + next.distance;
                if (newDist < dist[next.node]) {
                    dist[next.node] = newDist;
                    pq.add(new Node(next.node, newDist));
                }
            }
        }
    }
}

플로이드-워셜을 이용한 방법

플로이드 워셜은 노드들을 거치는 최단거리를 모두 다 구하게 된다. 그래서 노드들을 3번 탐색하게 되어 시간복잡도가 O(N^3)이 나오게 된다.
이 방법은 시간초과를 항상 유념해야 하는데, 문제조건에서 N은 200이하이기 때문에 O(10^6)정도가 나오게 되어 가능하다.

파이썬

def solution(n, s, a, b, fares):
    INF = int(1e9)
    cost = [[INF for _ in range(n + 1)] for _ in range(n + 1)]
    for i in range(1, n + 1):
        cost[i][i] = 0
    for fare in fares:
        start = fare[0]
        end = fare[1]
        val = fare[2]
        cost[start][end] = val
        cost[end][start] = val
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
    answer = INF
    for i in range(1, n + 1):
        answer = min(answer, cost[s][i] + cost[i][a] + cost[i][b])
    return answer

자바

import java.util.Arrays;
class Solution {
    static int[][] cost;
    public int solution(int n, int s, int a, int b, int[][] fares) {
        cost = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            Arrays.fill(cost[i], 1000000);
        }

        for (int[] fare : fares) {
            int start = fare[0];
            int end = fare[1];
            int val = fare[2];
            cost[start][end] = val;
            cost[end][start] = val;
        }

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (i != j) {
                        cost[i][j] = Math.min(cost[i][j], cost[i][k] + cost[k][j]);
                    }
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            cost[i][i] = 0;
        }

        int answer = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            answer = Math.min(answer, cost[s][i] + cost[i][a] + cost[i][b]);
        }

        return answer;
    }
}

정답 및 후기

python은 두 가지 방법 모두 통과하였지만, java의 경우 다익스트라에서 효율성에서 4개를 틀렸었다.
원인은 시간복잡도 때문인데, 시간초과가 나는 이유는 다익스트라에서 간선이 많은 경우에 문제가 생기는 것 같다.
간선이 많으면 위의 문제에서 시간복잡도가 초과될 수 있다.

항상 음수간선이 없으면 플로이드-워셜보다 다익스트라를 먼저 생각했는데(일반적으로 간선보다 노드 개수에 제한이 많은 경우가 많아서..)
이 경우는 노드가 200이하라 플로이드-워셜이 더 효과적인 문제였다.