[ 프로그래머스 합승 택시 요금 (Lv3) ] (C++)

프로그래머스의 합승택시요금(Lv3) 문제이다.

 

[ 문제풀이 ]

A와 B가 택시를 타고 도착지점으로 가야 할 때, 최저 택시 요금을 구해야 하는 문제이다.

먼저, 주어지는 변수들을 관리하는 것 부터 정답을 도출하는 과정까지 순차적으로 알아보자.

 

#1. 주어진 매개변수의 관리

먼저, 우리가 눈여겨봐야 할 주어진 매개변수는 아마 요금에 대한 정보가 들어있는 변수일 것이다.

요금에 대한 정보는 [A , B , C] 의 형태로 주어지며, A와 B로 가는데는 C만큼의 비용이 든다는 것을 의미한다.

따라서, 본인은 이를 벡터를 하나 만들어서 저장해 주었다.

2차원벡터의 형태처럼 "vector<vector<int>> Dist" 와 같은 형태로 하나의 변수를 선언해서 이를 관리해 주었다.

여기서 주의해야 할 것은 이 문제에서 주어진 맵에서 방향성은 없기 떄문에 A와 B가 C의 비용이 든다면,

B와 A 또한 C의 비용이 든다는 것이다.

다음과 같이 코드로 구현하였다.

void Make_Distance(vector<vector<int>> fares, vector<vector<int>> &Dist, int n)
{
	for (int i = 0; i < fares.size(); i++)
	{
		int S = fares[i][0];
		int E = fares[i][1];
		int D = fares[i][2];
		Dist[S][E] = D;
		Dist[E][S] = D;
	}
	for (int i = 1; i <= n; i++) Dist[i][i] = 0;
}

 

#2. 최저 비용 구하기

#1에서 저장해 놓은 비용정보를 통해서 각 정점간의 최소 비용을 구해야 한다.

특정 정점에서 나머지 정점에 대한 최소비용을 구하는 알고리즘으로는 다익스트라 , 벨만포드 알고리즘 등이 있지만 이 문제에서는 모든 정점간의 최소비용을 구해야 한다.

따라서 본인은 이 부분을 플로이드 워샬(Floyd-Warshall) 알고리즘을 통해서 구현해 주었다.

플로이드 워샬 알고리즘에 대한 설명글을 본인이 따로 포스팅 한 것이 없어서 간단하게만 설명하자면 다음과 같다.

일반적으로 3중 for문을 통해서 구현을 하게 된다.

for (int 중간점 = 1; 중간점 <= N; 중간점++)
{
	for (int 시작점 = 1; 시작점 <= N; 시작점++)
	{
		for (int 도착점 = 1; 도착점 <= N; 도착점++)
		{
			if : Dist[시작점][중간점] + Dist[중간점][도착점] < Dist[시작점][도착점]
				 => Dist[시작점][도착점] = Dist[시작점][중간점] + Dist[중간점][도착점]
		}
	}
}

위와 같이 구현을 하게 된다. 3중 for문에서 가장 바깥 for문은 시작점에서 도착점으로 가는 길목에 있는 중간점을 탐색해보기 위한 반복문이고, 가운데 for문은 시작점을, 가장 안쪽 for문은 도착점을 나타내는 for문이다.

위와 같이 3중 for문으로 탐색을 하면서, 시작점에서 도착점으로 다이렉트로 가는 경우보다, 중간점을 거쳐서 가는 경우가

더 최소의 비용이 드는 경우가 발생한다면, 최소의 비용을 갱신해 주면 된다.

이 문제에서의 플로이드 워샬 알고리즘은 다음과 같이 구현하였다.

void Floyd_Warshall(int n, vector<vector<int>> &Dist)
{
	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (i == j || i == k || k == j) continue;
				if(Dist[i][k] != INF && Dist[k][j] != INF) Dist[i][j] = Min(Dist[i][j], Dist[i][k] + Dist[k][j]);
			}
		}
	}
}

 

#3. 정답도출

이제 각 정점들간의 최소비용도 모두 구했으니 정답을 도출해보자.

정답은 다음과 같이 도출할 수 있다.

시작점을 'S' , 하나의 도착점을 'A', 또 하나의 도착점을 'B' 라고 표현했을 때,

모든 정점들을 반복하면서(모든 정점 = K라고 가정) 다음을 만족시키는 값을 구하면 된다.

Answer = Min(Answer, Dist[S][K] + Dist[K][A] + Dist[K][B])

위와 같이 탐색을 해서 가장 최소의 비용을 가지는 Answer을 찾으면 이것이 정답이 될 것이다.

 

[ 소스코드 ]

#include <string>
#include <vector>
 
#define INF 987654321
using namespace std;
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Make_Distance(vector<vector<int>> fares, vector<vector<int>> &Dist, int n)
{
    for (int i = 0; i < fares.size(); i++)
    {
        int S = fares[i][0];
        int E = fares[i][1];
        int D = fares[i][2];
        Dist[S][E] = D;
        Dist[E][S] = D;
    }
    for (int i = 1; i <= n; i++) Dist[i][i] = 0;
}
 
void Floyd_Warshall(int n, vector<vector<int>> &Dist)
{
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (i == j || i == k || k == j) continue;
                if(Dist[i][k] != INF && Dist[k][j] != INF) Dist[i][j] = Min(Dist[i][j], Dist[i][k] + Dist[k][j]);
            }
        }
    }
}
 
int solution(int n, int s, int a, int b, vector<vector<int>> fares) 
{
    int answer = 0;
    vector<vector<int>> Dist(n + 1, vector<int>(n + 1, INF));
    Make_Distance(fares, Dist, n);
    Floyd_Warshall(n, Dist);
 
    answer = Dist[s][a] + Dist[s][b];
    for (int i = 1; i <= n; i++)
    {
        if (Dist[s][i] != INF && Dist[i][a] != INF && Dist[i][b] != INF)
        {
            answer = Min(answer, Dist[s][i] + Dist[i][a] + Dist[i][b]);
        }
    }
    return answer;
}