[프로그래머스/Level 3/C++/2021 카카오 블라이드 채용] 합승 택시 요금

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

- 출처 : 프로그래머스 코딩 테스트 연습

프로그래머스

 

[문제 요약]

"무지"는 "어피치"와 귀가 방향이 비슷하여 택시 합승을 적절히 이용하면 택시요금을 얼마나 아낄 수 있을 지 계산해 보고 "어피치"에게 합승을 제안해 보려고 합니다.

- 위 예시 그림은 택시가 이동 가능한 반경에 있는 6개 지점 사이의 이동 가능한 택시노선과 예상요금을 보여주고 있습니다.
- 그림에서 A와 B 두 사람은 출발지점인 4번 지점에서 출발해서 택시를 타고 귀가하려고 합니다.

-  A의 집은 6번 지점에 있으며 B의 집은 2번 지점에 있고 두 사람이 모두 귀가하는 데 소요되는 예상 최저 택시요금이 얼마인 지 계산하려고 합니다.

 

[문제 조건]

• 지점갯수 n은 3 이상 200 이하인 자연수입니다.
• 지점 s, a, b는 1 이상 n 이하인 자연수이며, 각기 서로 다른 값입니다.
  • 즉, 출발지점, A의 도착지점, B의 도착지점은 서로 겹치지 않습니다.
• fares는 2차원 정수 배열입니다.
• fares 배열의 크기는 2 이상 n x (n-1) / 2 이하입니다.
  • 예를들어, n = 6이라면 fares 배열의 크기는 2 이상 15 이하입니다. (6 x 5 / 2 = 15)
  • fares 배열의 각 행은 [c, d, f] 형태입니다.
  • c지점과 d지점 사이의 예상 택시요금이 f원이라는 뜻입니다.
  • 지점 c, d는 1 이상 n 이하인 자연수이며, 각기 서로 다른 값입니다.
  • 요금 f는 1 이상 100,000 이하인 자연수입니다.
  • fares 배열에 두 지점 간 예상 택시요금은 1개만 주어집니다. 즉, [c, d, f]가 있다면 [d, c, f]는 주어지지 않습니다.
• 출발지점 s에서 도착지점 a와 b로 가는 경로가 존재하는 경우만 입력으로 주어집니다.

 

[문제 풀이]

일단 문제가 한 정점에서 다른 여러개의 정점으로의 최소 비용을 구해야하는 문제이기 때문에 아마도 플로이드-와샬 or 다익스트라를 이용해서 푸는 문제일 것이다.

 

필자는 플로이드-와샬로 문제를 풀었다.

 

먼저 각 정점별 다른정점으로의 최단 비용을 구한 뒤 생각해보았다.

 

시작지점 s에서 a,b로 가는 방법은 s에서 특정 지점 x라는 곳까지 같이 갔다가 x 지점에서 a,b로 각자 가는 방법이 있다. 이때 x라는지점이 있을 수도 있고 없을 수도 있다.(s에서 바로 각자 흩어 지는 경우)

 

이런 아이디어를 이용해 문제를 쉽게 풀 수 있다.

 

플로이드-와샬 방법으로 각 정점으로의 최단 비용을 저장해 놓고

x라는 값에 모든 지점을 하나씩 넣어본 뒤 최솟값을 출력하면 정답이 된다.

 

 for(int i=1; i<=n ;i++)
{
    if(mp[s][i] == INF || mp[i][a] == INF || mp[i][b] == INF) continue;
    ans = min(ans, mp[s][i] + mp[i][a] + mp[i][b]);
}

 

 

[소스 코드]

#include <string>
#include <vector>

#define INF 987654321

using namespace std;

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 0;
    
    vector<vector<int>> mp;
    mp.resize(n+1);
    for(int i=0; i<=n; i++) mp[i].resize(n+1);
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(i==j) continue;
            else mp[i][j] = INF;
        }
    }
    
    for(int i=0; i<fares.size(); i++)
    {
        int a_p = fares[i][0];
        int b_p = fares[i][1];
        int cost = fares[i][2];
        mp[a_p][b_p] = cost;
        mp[b_p][a_p] = cost;
    }
    //플로이드 와샬
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(k==i || i==j || j== k) continue;
                mp[i][j] = min(mp[i][j] , mp[i][k] + mp[k][j]);
            }
        }
    }
    
    int ans = INF;
    for(int i=1; i<=n ;i++)
    {
        if(mp[s][i] == INF || mp[i][a] == INF || mp[i][b] == INF) continue;
        ans = min(ans, mp[s][i] + mp[i][a] + mp[i][b]);
    }
    answer = ans;
    return answer;
}

굳