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

프로그래머스 합승 택시 요금 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

최대 200개의 지점 갯수를 가집니다.
시작지점 s, A의 도착지점 a, B의 도착지점 b를 가집니다.
이후로 지점들 간의 간선이 주어지는데 두 지점간의 간선 비용이 1개만 주어짐으로 보아 양방향으로의 이동 비용은 같습니다.
A와 B 두사람은 합승을 하여 원하는 지점으로 한 번의 비용을 내며 이동할 수 있습니다.
합승 후 각자 방향으로 택시를 탈 수도 있습니다.
s로부터 a, b의 최소값을 구해야합니다.

각 간선 간의 최소값을 구하는 것이 중요해보입니다.

문제 풀이

일단 A와 B는 자신이 원하는 지점에 최소로 도착해야 하며, 합승을 하여 비용이 더 낮아질 수 있는 여러 선택지를 생각하면 모든 간선의 최소값을 먼저 구하여 계산하는 것이 좋아보입니다.
그러기에 한 정점에서 모든 정점으로의 최솟값을 구하는 다익스트라 알고리즘과는 다르게
모든 정점에서 모든 정점으로의 최솟값을 구할 수 있는 플로이드 와샬 알고리즘을 사용합니다.

//배열 초기화
for(int i = 1; i <= n; i++)
{
    for(int j = 1; j <= n; j++)
    {
        if(i == j)
        {
            shortistPoint[i][j] = 0;
        }
        else
        {
            shortistPoint[i][j] = 100000000;
        }
    }
}
//배열에 간선들 등록
for(vector<int> v : fares)
{
    shortistPoint[v[0]][v[1]] = v[2];
    shortistPoint[v[1]][v[0]] = v[2];
}
//k = 거치는 간선, i, j는 시작과 도착 지점
for(int k = 1; k <= n; k++)
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(shortistPoint[i][j] > shortistPoint[i][k] + shortistPoint[k][j])
            {
                shortistPoint[i][j] = shortistPoint[i][k] + shortistPoint[k][j];
            }
        }
    }
}

이후 최솟값이 들어있는 배열을 가지고 시작점에서부터의 최단거리를 구합니다.
합승을 하지 않았을 시 (시작지점->A도착지점 + 시작지점->B도착지점)이 최단거리가 되겟지만
합승이 이루어졌을 시 (시작지점->합승도착지점 + 합승도착지점->A도착지점 + 합승도착지점->B도착지점)와 비교하며 최단거리를 구해야합니다. 합승도착지점은 시작지점을 제외한 모든 지점을 확인해야 합니다.

//합승해서 가는 지점과 도착한 지점으로부터 a, b 까지 요금의 최소값을 구함
answer = shortistPoint[s][a] + shortistPoint[s][b];
for(int i = 1; i <= n; i++)
{
    int t = shortistPoint[s][i] + shortistPoint[i][a] + shortistPoint[i][b];
    if(answer > t)
    {
        answer = t;
    }
}

전체 코드

플로이드 와샬 알고리즘을 사용하면 충분히 쉽게 풀이가 가능한 문제였습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 2100000000;
    int shortistPoint[201][201] = {0,};
    
    //배열 초기화
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(i == j)
            {
                shortistPoint[i][j] = 0;
            }
            else
            {
                shortistPoint[i][j] = 100000000;
            }
        }
    }
    //배열에 간선들 등록
    for(vector<int> v : fares)
    {
        shortistPoint[v[0]][v[1]] = v[2];
        shortistPoint[v[1]][v[0]] = v[2];
    }
    
    //k = 거치는 간선, i, j는 시작과 도착 지점
    for(int k = 1; k <= n; k++)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(shortistPoint[i][j] > shortistPoint[i][k] + shortistPoint[k][j])
                {
                    shortistPoint[i][j] = shortistPoint[i][k] + shortistPoint[k][j];
                }
            }
        }
    }
    //합승해서 가는 지점과 도착한 지점으로부터 a, b 까지 요금의 최소값을 구함
    answer = shortistPoint[s][a] + shortistPoint[s][b];
    for(int i = 1; i <= n; i++)
    {
        int t = shortistPoint[s][i] + shortistPoint[i][a] + shortistPoint[i][b];
        if(answer > t)
        {
            answer = t;
        }
    }
    
    return answer;
}

출저

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