[프로그래머스] 2021 카카오 블라인드 합승택시요금 [JAVA]

문제링크 : programmers.co.kr/learn/courses/30/lessons/72413

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

문제 해결법은 플로이드워셜로 가능하다는 것은 명확히 알았다. 다만 무한대의 거리를 어떻게 정의해야하는지 잘 모르겠다. 너무 크게 했더니 오버플로난 값을 min값으로 계산해서 문제 생기는가 하면 낮았을 때는 정답률이 낮았다. 숫자를 점점 높혀가다가 100만으로 설정하니 해결 됐다. 무한대의 거리를 100만으로 하면 통과하는 이유는 테케중에 x에서 y로 가는 최단거리가 100만보다 큰 경로가 없기 때문으로 이해했지만 맞는지 모르겠다. 어떤 위치에서 가장 먼 거리는 10만 * 200 = 1000만이 되어야 하는 것 아닌가?? 어쨌든 오버플로가 걱정이라면 long으로 계산해서 solution 함수에서 요구한 int로 리턴하는 방식을 사용하는게 낫겠다.

public int solution(int n, int s, int a, int b, int[][] fares) {
        int dist[][] = new int[n+1][n+1];
        for(int i=1;i<=n;i++){
        	for(int j=1;j<=n;j++){
        		if(i==j) dist[i][j] = 0;
        		else dist[i][j] = 1000000;
        	}
        }
        for(int i=0;i<fares.length;i++){
        	int start = fares[i][0];
        	int end = fares[i][1];
        	int cost = fares[i][2];
        	dist[start][end] = cost;
        	dist[end][start] = cost;
        }
        //플로이드워셜
        for(int i=1;i<=n;i++){
        	for(int j=1;j<=n;j++){
        		for(int k=1;k<=n;k++){
        			if(dist[j][i] + dist[i][k] < dist[j][k]){
        				dist[j][k] = dist[j][i] + dist[i][k];
        			}
        		}
        	}
        }
        int ans = 1000000000;
        for(int i=1;i<=n;i++){
        	int tempAns = dist[s][i] + dist[i][a] + dist[i][b];
        	ans = Math.min(tempAns, ans);
        }
        
        return ans;
    }
	public static void main(S