[프로그래머스](플로이드 워셜)합승 택시 요금 (C++ / 2021 KAKAO BLIND)

합승 택시 요금 (Level 3)

문제

전체 문제 보기

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

접근법

이 문제는 합승을 통해서(혹은 합승을 하지 않을 수 있음) 가장 요금을 절약할 경우의 금액을 출력해야 합니다. 예를 들면 3번 노드까지 합승한 경우라면, (4 → 3) + (3 → 2) + (3 → 6) 3개의 최소 요금을 계산해야 합니다. 이를 조금 더 일반화해서 i번 노드 까지 합승한 경우를 아래와 같은 상황을 계산해야 합니다. 아래의 값들을 계산하여 가장 작은 값을 출력하면 됩니다.

• for i = 1 to N
  • (s → i) + (i → A) + (i → B)

위 반복문에는 합승을 하지 않는 경우도 포함되어 있습니다. 만약 시작 노드s가 4 라면, i가 4일 경우 (s → i)는 (4 → 4)가 됩니다. 밑에서 다루겠지만 (4 → 4)는 항상 0입니다.

 

이를 코드로 표현하면 다음과 같습니다.

    // graph[a][b] : a->b 로 이동하는 최소 요금
    vector<vector<int>> graph(MAX_N);

    // ... 중략 ...

    answer =  INF ;
    for (int i = 1; i <= n; ++i)
    {
        int share = (graph[s][i] + graph[i][a] + graph[i][b]);
        answer = min(answer, share);
    }

알고리즘 선택

각 정점에서 정점마다 최소 요금을 구하가 위해서는 플로이드 워셜 알고리즘을 사용할 수 있습니다. 플로이드 워셜 알고리즘은 각 정점에서 이동 가능한 모든 정점으로 최소거리를 \(O(N^3)\) 시간 복잡도로 계산할 수 있는 알고리즘입니다. 상당히 느린 알고리즘에 속하지만 문제에서 주어진 N의 크기가 200으로 작기 때문에 이번 문제에서 사용할 수 있습니다.

 

플로이드 워셜 알고리즘은 다음과 같습니다. 여기서 앞서 언급한 대로 자기 자신으로의 이동 요금을 0으로 설정하는 부분도 포함되어 있습니다.

void FloydWarshall(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        // 자기 자신으로 이동 요금을 0으로
        graph[i][i] = 0;
    }

    for (int i = 1; i <= n; ++i)
    {
        for (int from = 1; from <= n; ++from)
        {
            for (int to = 1; to <= n; ++to)
            {     
                // from -> to 보다 from -> i -> to 비용이 더 적다면, 비용을 갱신한다.
                if (graph[from][to] > graph[from][i] + graph[i][to])
                    graph[from][to] = graph[from][i] + graph[i][to];
            }
        }
    }
}

전체 코드

#include <string>
#include <vector>
#include <array>
#include <queue>

#define INF 20'000'001
#define MAX_N 201
using namespace std;

// graph[a][b] : a->b 로 이동하는 최소 요금
vector<vector<int>> graph(MAX_N);

void InputFares(vector<vector<int>>& fares)
{
    for (auto& row : graph)
    {
        // 모든 요금을 INF 값으로 초기화
        row.resize(MAX_N, INF);
    }
    for (auto info : fares)
    {
        int a = info[0];
        int b = info[1];
        int fare = info[2];

        graph[a][b] = fare;
        graph[b][a] = fare;
    }
}
void FloydWarshall(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        // 자기 자신으로 이동 요금을 0으로
        graph[i][i] = 0;
    }

    for (int i = 1; i <= n; ++i)
    {
        for (int from = 1; from <= n; ++from)
        {
            for (int to = 1; to <= n; ++to)
            {     
                // from -> to 보다 from -> i -> to 비용이 더 적다면, 비용을 갱신한다.
                if (graph[from][to] > graph[from][i] + graph[i][to])
                    graph[from][to] = graph[from][i] + graph[i][to];
            }
        }
    }
}
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 0;

    InputFares(fares);

    // 최단거리 계산
    FloydWarshall(n);

    answer =  INF ;
    for (int i = 1; i <= n; ++i)
    {
        int share = (graph[s][i] + graph[i][a] + graph[i][b]);
        answer = min(answer, share);
    }

    return answer;
}

성능 평가

이번 풀이에서는 플로이드 워셜 알고리즘을 사용하였습니다. 플로이드 워셜 알고리즘은 3중 for문으로 이루어져있으며, 각 for문은 노드의 개수 \(N\) 만큼 반복합니다. 따라서 \(O(N)\) 시간 복잡도를 가진 알고리즘입니다. 공간 복잡도를 살펴보기 위해서 graph 배열을 보면 전체 노드 개수만큼의 이중배열을 사용합니다. 따라서 공간 복잡도는 \(O(N^2)\)임을 알 수 있습니다.