[Algorithm/Java] kakao 2021 합승택시요금

import java.util.*;
class Solution {
    public static int solution(int n, int s, int a, int b, int[][] fares) {

        final int MAX = 100000001;
        int [][] map = new int[n+1][n+1];

        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                map[i][j]=MAX;
            }
            map[i][i]=0;
        }

        for(int i=0; i<fares.length; i++){

            map[fares[i][0]][fares[i][1]] = fares[i][2];
            map[fares[i][1]][fares[i][0]] = fares[i][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 = MAX;
        for(int i=1; i<=n; i++){
            if(answer > map[s][i] + map[i][a]+ map[i][b]){
                answer = map[s][i]+map[i][a]+map[i][b];
            }
        }
        return answer;
    }

}

다익스트라 하거나 플로이드와샬로 최소거리 구해준다음

 

   if(answer > map[s][i] + map[i][a]+ map[i][b]){
                answer = map[s][i]+map[i][a]+map[i][b];
            }

이걸해주면되는거여따. .

 

 

<노션에적은 내용>

플로이드와샬은 하고나서 answer = map[s][i]+map[i][a]+map[i][b];

시작점→특정노드 + 특정노드→a + 특정노드→b 최솟값 더한거로 갱신한다는 비슷한 생각은 했는데

특정노드로 옮겨가는 동안 뭔가 해줘야될까싶어서 큐에다가 노드 넣고 빼고,, 복잡하게 생각했었다

근데 그냥 최소거리 다익스트라나 플로이드 이용해서 구하고 저 식 모든 노드에대해서 해주면 되는거였음.

MAX값이 100000이 아니라 다 더했을때도 MAX여야되니까 값을 더 크게 잡아야 되는것, 자기자신으로 가는거리는 0이어야되는것 주의

병사 찾기?문제 힌트보고 천천히 생각해서 한번에 구현은 했다.

0일때 0보다 클때 0보다 작을때의 분기 나눠줘야하는 점 찾으려니까 좀 오래걸렸다ㅣ. 처음부터 잘 생각할것