[Programmers] 합승 택시 요금

문제 설명

Key Point

- 특정 경로의 최대 비용은 20,000,000원 (지점 개수(n) 최대 200개 ✖ 요금(f) 최대 100,000원)
- 목적 지점 A, B에 모두 도달하는 경로 중 최소 비용의 경로 탐색
- 최단 경로 탐색 알고리즘 사용 (다익스트라[Dijkstra], 플로이드-워셜[Floyd-Warshall] 알고리즘)
- 출발 지점(s)에서 특정 지점(x)으로 이동 후 목적 지점A(x → a), 목적 지점B(x → b)로 이동하는 경로 중 최소한의 비용을 탐색

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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

해당 게시글은 프로그래머스의 코딩 테스트를 풀어가는 과정을 작성한 글로 정답이 포함되어 있습니다.
먼저 문제를 풀어보신 후 열람할 것을 추천드리며, 저와 다른 방식으로 접근하셨다면, 이러한 방식도 가능하다는 것을 알아가시는 데 도움이 되시기를 바랍니다.

접근 방식

해당 알고리즘을 참고하기 전에는, 추출이 용이하도록 각 지점 별 소요 비용을 Map 형태로 저장한 뒤, 다음 세 가지 경우에 해당하는 값을 추출하였습니다.
1. 출발 지점(s) → 목적 지점A(a) 만을 포함하는 경로 중, 최소 비용의 경로 추출
2. 출발 지점(s) → 목적 지점B(b) 만을 포함하는 경로 중, 최소 비용의 경로 추출
3. 목적 지점A(a), 목적 지점B(b) 모두를 통과하는 경로 중, 최소 비용의 경로 추출

각 경우에 해당하는 값 도출 후 1+2의 값과 3의 값 중에서 최소 값을 결과로 반환하였으나 특정 지점(x)까지 이동 후 각자 목적지로 향하는 경로를 고려하지 못해 문제를 해결하지 못하였습니다😕

이후 최단 경로 탐색 알고리즘을 검색해 본 뒤, 다익스트라(Dijkstra) 알고리즘을 알게 되었고, 해당 알고리즘을 접목하여 문제를 해결하게 되었습니다.

다익스트라(Dijkstra) 알고리즘

다수의 지점 중 특정 지점과 지점을 이동하는 경로의 모든 비용 중 최소 비용 도출해 갱신해 나아가는 알고리즘.
알고리즘에 대한 보다 자세한 설명은 아래 References의 포스팅을 참고하시면 상세히 설명되어 있으니 참고하시면 좋을 것 같습니다.

문제 적용 예시

해당 문제는 목적 지점이 두 개이기 때문에, 모든 경로 별 비용을 산출해야 합니다.

모든 경로 별 비용을 산출한 뒤 출발 지점(s)에서 특정 지점(x)으로 이동 후 목적 지점A(x → a), 목적 지점B(x → b)로 이동하는 경로 중 최소한의 비용을 구해내면 됩니다. (특정 지점은 목적 지점A 또는 목적 지점B가 될 수도 있습니다)

1. 지점 별 이동 비용(fares)을 2차원 배열 형태로 재정의

위 표의 각 행과 열은 지점을 의미하며, 각 셀은 지점 간의 이동 시 필요 비용을 뜻하게 됩니다.

※ [3, 3]이 0인 이유는 지점3 → 지점3은 위치 변동이 없기 때문에 비용이 0이 되게 됩니다.

※ [1, 2] [2, 1]이 20,000,000인 이유는 지점1 → 지점2 또는 지점2 → 지점1 의 경우 주어진 이동 비용(fares)로 만 보았을 때 이동이 불가능하기 때문에 경로 간 최대 비용을 적용합니다.

이동 비용(farse)를 위 표와 같이 2차원 배열로 변환하고자 한다면 다음과 같은 순서를 따르게 됩니다.

1-1. 지점의 개수에 해당하는 2차원 배열 routeArr 생성

1-2. 이동 비용(farse[c, d, f])를 차례대로 순회하며 지점 간 이동 비용을 routeArr에 입력, 단 지점 간 이동은 양방향이기 때문에 양방향 모든 값을 입력 (routeArr[c][d] = f, routeArr[d][c] = f)

1-3. 생성한 2차원 배열을 모두 순회하며 위치 변동이 없는 지점이 아니고, 값이 0일 경우 (Java의 경우 int 배열의 초기값은 0으로 설정) 현재로서는 이동 방안이 없기 때문에 최대 비용(20,000,000)를 입력

2. 다익스트라 알고리즘을 이용한 지점 간 이동 시 최소 비용 갱신

해당 알고리즘을 적용하기 위해서는 아래 규칙만 적용하면 간단합니다.

※ 한번 확인 한 지점은 다시 확인하지 않는다.

※ 이동 비용이 최소인 지점부터 갱신한다.

※ 지점A → 지점B로 이동하는 비용과 지점A → 지점X → 지점B 비용을 비교하여 낮은 값으로 갱신한다.

예시를 보며 위 순서를 적용하면 다음과 같습니다.

1. 지점1 → 지점4로 가는 비용이 10으로 가장 낮기 때문에 routeArr[0][3]을 기준으로 정의

2. 지점1 → 지점4(routeArr[0][3]) 지점4 → 지점2(routeArr[1][3])로 가는 비용은 10+ 66으로 77이지만, 지점1 → 지점2(routeArr[0][1])로 가는 비용은 20,000,000이기 때문에, 지점1 → 지점2(routeArr[0][1]) 의 이동 비용을 77로 갱신

해당 방식을 반복하며, 배열 내 모든 원소를 순회하게 되면 다음 표와 같이 최소 비용이 갱신됩니다.

3. 각 지점을 중간 지점으로 설정한 뒤, 목적 지점 A, B로 이동하는 최소 비용 추출

마지막으로 각 지점을 순회하며 출발 지점(s)에서 중간 지점(x)로 이동 후, 목적 지점A(a) 목적 지점B(b) 로 다시 이동하는 비용을 산출하여 가장 최소값을 구합니다.

따라서 위 예시 문제의 출발 지점4에서 목적 지점2, 6으로 이동하는 경우의 수 중 최소 비용은 82가 됩니다.

풀이

class Solution {

    public int solution(int pointCnt, int startPoint, int destA, int destB, int[][] fares) {
        int[][] routeArr = initRouteArr(fares, fares.length, pointCnt);
        int index, cost, minCost = 20000000;
        boolean[] isCheck;

        /* 2. 다익스트라 알고리즘을 이용한 지점 간 이동 시 최소 비용 갱신 */
        for (int i = 0; i < pointCnt; i++) {
            // 2.1 지점 확인 여부 초기화
            isCheck = new boolean[pointCnt];
            // 제자리 지점은 확인하지 않도록 설정
            isCheck[i] = true;

            for (int j = 0; j < pointCnt; j++) {
                // 2.2 확인하지 않은 지점 중 최소의 비용으로 이동할 수 있는 지점 탐색
                index = nextIdx(routeArr, i, pointCnt, isCheck);
                // 확인할 지점의 금액 산출
                cost = routeArr[i][index];

                for (int k = 0; k < pointCnt; k++) {
                    // 2.3 확인할 지점의 비용 + 지점에서의 이동 비용이 기준점에서 이동 비용보다 작을 경우 갱신
                    if (routeArr[k][index] + cost < routeArr[i][k]) {
                        routeArr[i][k] = routeArr[k][index] + cost;
                    }
                }
            }
        }

        /* 3. 각 지점을 중간 지점으로 설정한 뒤, 목적 지점 A,B로 이동하는 최소 비용 추출 */
        for (int i = 0; i < pointCnt; i++) {
            cost = routeArr[startPoint - 1][i] + routeArr[i][destA - 1] + routeArr[i][destB - 1];
            if (cost < minCost) {
                minCost = cost;
            }
        }

        return minCost;
    }

    /* 1. 지점 별 이동 비용를 2차원 배열 형태로 재정의 */
    private int[][] initRouteArr(int[][] farse, int farseLen, int pointCnt) {

        // 1-1. 지점 개수에 해당하는 2차원 배열 생성
        int[][] routeArr = new int[pointCnt][pointCnt];

        // 1-2. 지점 간 이동 비용 입력
        for (int i = 0; i < farseLen; i++) {
            routeArr[farse[i][0] - 1][farse[i][1] - 1] = routeArr[farse[i][1] - 1][farse[i][0] - 1] = farse[i][2];
        }

        // 1-3. 이동 방안이 없는 경우 최대 비용 입력
        for (int j = 0; j < pointCnt; j++) {
            for (int k = 0; k < pointCnt; k++) {
                if (j != k && routeArr[j][k] == 0) {
                    routeArr[j][k] = 20000000;
                }
            }
        }

        return routeArr;
    }

    private int nextIdx(int[][] routeArr, int point, int runCnt, boolean[] isCheck) {
        int minVal = 20000000;
        int minIdx = runCnt - 1;

        for (int i = 0; i < runCnt; i++) {
            if (!isCheck[i] && minVal > routeArr[point][i]) {
                minVal = routeArr[point][i];
                minIdx = i;
            }
        }

        isCheck[minIdx] = true;

        return minIdx;
    }

}

References

https://m.blog.naver.com/ndb796/221234424646

23. 다익스트라(Dijkstra) 알고리즘

다익스트라(Dijkstra) 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest P...

blog.naver.com