[프로그래머스] 합승 택시 요금 - JAVA

[문제]

• 2021 KAKAO BLIND RECRUITMENT 문제

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

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

 

[풀이]

• 사용 알고리즘: 플로이드-와샬 알고리즘

그래프 문제이며 그 중에서 모든쌍 최단 경로 알고리즘인 플로이드-와샬을 응용하는 문제이다. 

어느 지점까지는 합승을 하며, 그 다음부터는 A와 B가 각자의 길로 가면 된다.

 

S -> T(합승 도착지) 까지 최단 경로를 구하고, 또, T -> A와 T -> B의 최단 경로를 구해서 3개를 더하면 최소 요금이 나온다. 

 

그럼 합승 도착지는 n개의 지점 중에 어디일까?

n개 모두 합승 도착지가 될 수 있다. 그러니 모두 구해봐야 하고 각 합승 도착지에서 A,B로 가는 최단 경로를 구해봐야 한다. 

        int minFare = Integer.MAX_VALUE;
        // 각 지점을 합승 구간이라고 가정하고 택시요금을 계산해봄
        for (int i = 1; i <= n; i++) {
            int share = resultArray[s][i]; // 합승 구간 요금

            int aFare = resultArray[a][i]; // 합승 구간 -> a까지 요금
            int bFare = resultArray[b][i]; // 합승 구간 -> b까지 요금

            int sum = share + aFare + bFare;
            minFare = Math.min(minFare, sum);
        }

 

*주의사항*

처음에 채점을 했을때 몇개의 케이스에서 실패가 떴다. 

플로이드 와샬은 모든 지점사이의 최단 경로를 구하는 것이기 때문에 최초에 각 경로는 무한대값으로 초기화시켜준다. 

하지만 말이 무한대지, 코드에서는 충분이 큰값 (문제에서 이 수만큼은 나올 수 없다하는)으로 초기화를 시켜줘야 한다. 

나는 처음에 충분히 큰 값으로 초기화하지 않아서 실패가 떴고, 아래 조건을 보고 무한대값을 100000 * n(지점의 수)으로 수정했더니 모두 정답이 나왔다. 

• 요금 f는 1 이상 100,000 이하인 자연수입니다.

 

[코드]

package kakao.blind2021;

import java.util.Arrays;

public class Test01 {
    public static void main(String[] args) {

       /* int n = 6;
        int s = 4;
        int a = 6;
        int b = 2;
        int[][] fares = {{4, 1, 10}, {3, 5, 24}, {5, 6, 2}, {3, 1, 41}, {5, 1, 24}, {4, 6, 50}, {2, 4, 66}, {2, 3, 22}, {1, 6, 25}};*/

        int n = 7;
        int s = 3;
        int a = 4;
        int b = 1;
        int[][] fares = {{5, 7, 9}, {4, 6, 4}, {3, 6, 1}, {3, 2, 3}, {2, 1, 6}};

        int answer = solution(n, s, a, b, fares);
        System.out.println(answer);
    }



    public static int solution(int n, int s, int a, int b, int[][] fares) {
        int INFINITE = 100000 * n;
        int answer = 0;

        // 2차원 배열 생성
        int[][] nArray = new int[n + 1][n + 1];
        for (int i = 0; i < nArray.length; i++) {
            Arrays.fill(nArray[i], INFINITE);
            nArray[i][i] = 0;
        }

        for (int i = 0; i < fares.length; i++) {
            int[] fare = fares[i];
            int x = fare[0];
            int y = fare[1];
            int value = fare[2];

            nArray[x][y] = value;
            nArray[y][x] = value;
        }

        // 결과 그래프
        int[][] resultArray = new int[n + 1][n + 1];
        for (int i = 0; i < resultArray.length; i++) {
            for (int j = 0; j < resultArray[0].length; j++) {
                resultArray[i][j] = nArray[i][j];
            }
        }

        // k = 거쳐가는 노드
        for (int k = 1; k <= n; k++) {
            // i = 출발 노드
            for (int i = 1; i <= n; i++) {
                // j = 도착 노드
                for (int j = 1; j <= n; j++) {
                    if (resultArray[i][k] + resultArray[k][j] < resultArray[i][j]) {
                        resultArray[i][j] = resultArray[i][k] + resultArray[k][j];
                    }
                }
            }
        }

        int minFare = Integer.MAX_VALUE;
        // 각 지점을 합승 구간이라고 가정하고 택시요금을 계산해봄
        for (int i = 1; i <= n; i++) {
            int share = resultArray[s][i]; // 합승 구간 요금

            int aFare = resultArray[a][i]; // 합승 구간 -> a까지 요금
            int bFare = resultArray[b][i]; // 합승 구간 -> b까지 요금

            int sum = share + aFare + bFare;
            minFare = Math.min(minFare, sum);
        }

        return minFare;
    }
}

 

참고
https://www.youtube.com/watch?v=leXszEFCKWM