[프로그래머스] 합승 택시 요금 / 2021 KAKAO BLIND RECRUITMENT - JAVA

🖇️ 문제 링크

코딩테스트 연습 - 합승 택시 요금

밤늦게 귀가할 때 안전을 위해 항상 택시를 이용하던 무지는 최근 야근이 잦아져 택시를 더 많이 이용하게 되어 택시비를 아낄 수 있는 방법을 고민하고 있습니다. "무지"는 자신이 택시를 이용할 때 동료인 어피치 역시 자신과 비슷한 방향으로 가는 택시를 종종 이용하는 것을 알게 되었습니다.

https://programmers.co.kr/learn/courses/30/lessons/72413

 

---

⌨️ 코드

import java.util.*;

class Solution {
    final int INF = (int)1e8;
    public int solution(int n, int s, int a, int b, int[][] fares) {
       	int[][] adj = new int[n + 1][n + 1];
        
        for(int i = 1; i <= n; i++) {
            Arrays.fill(adj[i], INF);
            adj[i][i] = 0;
        }
        
       	for(int[] fare : fares) {
            int u = fare[0];
            int v = fare[1];
            int cost = fare[2];
            
           	adj[u][v] = cost;
            adj[v][u] = cost;
        } 
        
        for(int k = 1; k <= n; k++) {
            for(int i = 1; i <= n; i++) {
               	if(adj[i][k] == INF) continue;
                for(int j = 1; j <= n; j++)
                   	adj[i][j] = Math.min(adj[i][j], adj[i][k] + adj[k][j]); 
            }
        }
        
        int ret = INF;
        for(int i = 1; i <= n; i++)
           	ret = Math.min(ret, adj[s][i] + adj[i][a] + adj[i][b]);
        
        return ret;
    }
}

 

Uploaded by Notion2Tistory v1.1.0