프로그래머스 합승 택시요금 문제풀이 Java 자바 상세풀이

합승 택시요금

문제설명

 

문제는 위와 같습니다.

주어진 지점 s 에서 출발 할 때 목적지 a와 b가 도착하는 경로중에 합승을 통하거나 또는 통하지 않고 최소비용을 산출하면 됩니다.

fares 에서는 각 지점 c 에서 d 까지의 요금을 f로 나타내어 주어집니다.

또한 문제에서는 c,d,f 로 주어지고 양방향이지만 d,c,f는 주어지지 않습니다.

-> 따라서 코드 작성시 양방향으로 작성해주어야 합니다.

 

제한사항

 

문제풀이

class Solution {
   int[][] Dist = new int[200][200]; // 지점갯수 n 최댓값 3이상 200이하
    static final int INF = 200000000; // 간선당 최대 금액 10만 * 지점 최대 200개 (중첩이 되기 때문에 일반적인 무한대 사용시 초과)

    void floyd(int n) {
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if(Dist[i][j] > Dist[i][k] + Dist[k][j]) {
                        // 경유지 k 를 거쳐 i 에서 j 로 가는 것이 직접 i 에서 j 까지 값보다 적으면 업데이트
                        Dist[i][j] = Dist[i][k] + Dist[k][j];
                    }
                }
            }
        }
    }

    public int solution(int n, int s, int a, int b, int[][] fares) {
        for (int i = 0; i < n; i++) { // 1. 이중배열 Dist 초기화
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    Dist[i][j] = 0;
                } else {
                    Dist[i][j] = INF;
                }
            }
        }

        for (int[] edge : fares) { // 2. 간선 비용 업데이트
            Dist[edge[0] - 1][edge[1] - 1] = edge[2];
            Dist[edge[1] - 1][edge[0] - 1] = edge[2];
        }

        floyd(n); // 3. 플로이드 와샬
        s--;
        a--;
        b--;

        int answer = INF;

        for(int k = 0; k < n; k++) { // 4. 비교하며 최소비용 산출
            answer = Math.min(answer, Dist[s][k] + Dist[k][a] + Dist[k][b]);
        }

        return answer; // 5. 결과값 반환
    }
}

문제풀이는 유튜브 ezsw 님의 풀이를 참고하여 재작성 해보았습니다.

 

1. 주어진 제한사항에서 n 은 최소 3 최대 200으로 주어지기 때문에 최대값으로 생성해주었습니다. 그 이후 자기 자신 지점 (i == j)은 비용이 들지 않으므로 0 으로 초기화를 해주고 그 이외의 값은 임의의 INF 값으로 주었습니다. 여기서 INF은 일반적으로 아주 큰 값을 사용하지만 추후 비용 계산시 중첩으로 더해질 수 있기 때문에 값의 범위를 초과하는 것을 방지하고자 문제에서 주어진 최대 200개의 간선 * 최대 비용 100000 을 곱하여 주었습니다.

 

2. for문을 통해 각각의 지점간의 비용을 주어진 fares[] 로부터 입력해줍니다. 이때 양방향이지만 [c,d,f]의 정보만 주어지기 때문에 [d,c,f] 값도 입력해주도록 합니다. 이때 주어진 값은 1부터 시작하지만 Dist 배열은 0부터 시작하기 때문에 각각의 위치에서 -1을 해줍니다.

 

3. 플로이드 와샬 알고리즘을 통해 경유지 k, 출발지 i, 목적지 j 까지 갈 때의 비용을 3중 for문을 통해 작성해줍니다. 만약 출발지 i 에서 바로 j로 가는 비용보다 i에서 k로 간 후에 k 에서 j로 가는 비용이 직선비용 Dist[i][j]보다 적다면 값을 업데이트 해줍니다.

 

4. 2번과 마찬가지로 0부터 시작했기 때문에 주어진 값에서 1씩 빼준 후 Math.min 메소드를 통해 플로이드 와샬로 작성된 최단 경로별로 최소비용을 찾아줍니다.

 

5. 4번에서 찾은 최소비용을 반환해줍니다.

 

 

출처 : 유튜브 ezsw