합승 택시 요금

코딩 문제

https://campus.programmers.co.kr/tryouts/185298/challenges

문제 파악

어떤 사람들이 각각 목적지로 가야 되는데, 처음엔 같이 택시를 타고 가다가 중간에 갈라질 수 있다. 이때 전체 요금이 최소가 되도록 경로를 선택해야 함.

입력
• n: 지점의 개수 (정점 개수)
• s: 출발지
• a, b: 각각의 목적지
• fares: 요금 정보 ([출발, 도착, 요금])

접근 방법

1.	모든 정점에서 모든 정점으로의 최단 거리가 필요하니까 → 플로이드 워셜 사용!
2.	s → a + s → b처럼 각각 따로 가는 경우도 고려해야 하고, s → i까지 같이 가고, i → a, i → b로 따로 가는 케이스도 고려해야 해.
3.	그중 요금이 제일 적은 케이스를 골라서 answer로 반환하면 끝!

코드 구현

import java.util.*;

class Solution {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int[][] map = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            Arrays.fill(map[i], 200 * 100_000);
            map[i][i] = 0;
        }

        for (int[] fare : fares) {
            map[fare[0]][fare[1]] = fare[2];
            map[fare[1]][fare[0]] = fare[2];
        }

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (map[i][j] > map[i][k] + map[k][j]) {
                        map[i][j] = map[i][k] + map[k][j];
                    }
                }
            }
        }

        int answer = map[s][a] + map[s][b];

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

        return answer;
    }
}