[Lv.3] 합승 택시 요금

class Solution {

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

        int[][] nodeFare=new int[n+1][n+1];

        for(int i=1;i<=n;i++) {
            for (int j = 1; j <=n; j++) {
                nodeFare[i][j]=(i==j)? 0:20000000;
            }
        }
        for (int i = 0; i < fares.length; i++) {
            int target1=fares[i][0];
            int target2=fares[i][1];
            int fare=fares[i][2];
            nodeFare[target1][target2]= nodeFare[target2][target1]=fare;
        }

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

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




        return answer;
    }
}

---

코드 자체는 생각보다 깔끔하게 작성될 수 있는 문제였다.

근데, 그래프 탐색 기법이 생각이 잘 안나서 그냥 dfs, bfs로 시도해보다 문제를 잘못읽었다는걸 알아차리고 질문게시판을 뒤져봤다.

대부분 그래프 탐색 기법(다익스트라, 플루이드)로 푼 것 같아 보였다.

그래서, 플루이드 (bottom-up)으로 푼 풀이를 읽어보고 코드를 작성하니 정답이 되었다...

그래프 탐색 기법도 좀 공부하고 익혀야겠다..