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

난이도: Level 3

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

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

2021 kakao Blind Recruitment 기출문제입니다.

기본적으로는 노드 간 거리가 주어졌을 때, 출발지로부터 목적지까지의 최단 거리를 구하는 류의 문제입니다.

 

다만 이 문제는 효율성 테스트까지 있어서 시간복잡도를 잘 고려해서 로직을 짜야 하는데요.

문제의 접근 방법을 생각해 봅시다.

 

출발지 S, A의 목적지 A, B의 목적지 B, A와 B가 합승하는 경우, 합승이 끝나는 지점을 C라고 하겠습니다.

• 합승을 하지 않는 경우, S->A + S->B (S에서 A, B로 각각 가는 최단 거리) 의 합을 구합니다.
• 합승을 했다가 목적지인 곳에서 합승을 마치는 경우, S->A + A->B 혹은 S->B + B->A를 구합니다.
• 합승을 했다가 목적지가 아닌 곳에서 합승을 마치는 경우, S->C + C->A + C->B를 구합니다.

목적지가 아닌 곳에서 합승을 마치는 경우, C를 어디로 골라야 거리의 합이 최단 거리가 될지 알 수 없습니다.

따라서 노드 1 ~ n을 모두 테스트 해 보게 됩니다.

 

노드의 개수가 최대 200개이며, 이 경우 fares는 (200 * 199) / 2 = 19,900개를 가질 수 있습니다.

다익스트라 알고리즘은 시간 복잡도가 O(E log V)가 됩니다. E는 n^2 / 2 가 되므로, O (n^2 log n)이라고 할 수 있습니다.

문제는 이 다익스트라 알고리즘을 돌리는 횟수가 엄청나게 되는데요.

모든 C에 대해 다익스트라 올고리즘을 돌리는 경우, 200 * 3 (S->C, C->A, C->B) 번 돌아가게 됩니다.

이것 역시 n번만큼 돌아가므로, O(n^3 log n)이 되었다고 할 수 있습니다.

다행히 데이터 크기가 많지는 않지만, 시간복잡도가 꽤 큰 편입니다.

 

저는 따라서, 다익스트라 알고리즘으로 접근한다면 시간이 많이 걸릴 것으로 판단하였습니다.

위 문제는 모든 노드에 대해 다른 노드로의 최단 거리를 자주 참조하게 되고, 같은 계산을 또 하는 경우도 존재하므로, 다익스트라 알고리즘보다는 플로이드-워셜 알고리즘이 더 적합하다고 생각했습니다.

플로이드-워셜 알고리즘은 제 블로그에서 내용에 대해 작성한 바 있습니다.

 

(실제 카카오 기술 블로그에 올라온 문제 해설 (4번) 에서는, 플로이드-워셜을 써서 풀어도 되고 다익스트라를 써서 풀어도 된다고 합니다.

즉 최단거리를 구하는 알고리즘은 둘 중 어떤 걸 써도 상관없고, 문제 접근 방법을 잘 생각해 내는 것이 핵심인 문제입니다.)

 

플로이드-워셜 알고리즘은 O(n^3)의 시간 복잡도를 가지는데, n이 최대 200이므로 n^3은 최대 8,000,000이 됩니다.

이렇게 한 번 계산해 두면 이후에는 값을 참조만 하면 되기 때문에, 저는 플로이드-워셜 알고리즘으로 접근하였습니다.

 

코드 링크: GitHub

GitHub - kchung1995/code_test_personal: 혼자 코딩 테스트 공부를 하며 사용하는 저장소

// 문제 링크: https://programmers.co.kr/learn/courses/30/lessons/72413
#include <string>
#include <vector>
#include <algorithm>

#define MAX_N 201
#define INF 1e8

using namespace std;

int d[MAX_N][MAX_N];

void floydWarshall(int &n, vector<vector<int> > &fares) {
    
    // 초기 주어진 거리 설정
    for (auto &next : fares) {
        d[next[0]][next[1]] = next[2];
        d[next[1]][next[0]] = next[2];
    }
    
    // 플로이드 와셜 3중 for문
    for (int k = 1; k <= n; k++) {
        for (int a = 1; a <= n; a++) {
            for (int b = 1; b <= n; b++)
                d[a][b] = min(d[a][b], d[a][k] + d[k][b]);
        }
    }
}

void init(int &n) {
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            d[i][j] = INF;
        }
    }
}

// 지점 (노드)의 수 3 <= n <= 200
// s, a, b는 각각 서로 다른 n 이하의 자연수, 서로 겹치지 않는다.
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    
    int answer = INF;
  
    init(n);
    // 플로이드 와셜 알고리즘
    floydWarshall(n, fares);
    
    // 환승점 c를 기준으로, a와 b가 갈라지는 경우
    for (int c = 1; c <= n; c++) {
        answer = min(answer, d[s][c] + d[c][a] + d[c][b]);
    }
    // 환승점이 a 또는 b의 목적지인 경우
    answer = min(answer, min(d[s][a] + d[a][b], d[s][b] + d[b][a]));
    // 합승을 하지 않을 때 더 저렴한 경우, 합승을 하지 않는다.
    answer = min(answer, d[s][a] + d[s][b]);
    
    return answer;
}

 

이 문제는 정확성 50, 효율성 50점이 각각 주어지는 문제였습니다.

아마 효율성 때문에 Level 3으로 분류가 되었던 것 같은데, 플로이드-워셜 알고리즘을 알고 있다면 쉽게 풀 수 있는 문제라고 생각합니다.