[카카오 블라인드 2021] 합승 택시 요금 :: c++ 코드, 문제 해석, 플루이드 와샬

합승 택시 요금

난이도 : ★★★☆☆

걸린 시간 : 못 풀었음

문제

합승 택시 요금 링크

 

해설

그래프 최단 경로 알고리즘 dijkstra나 floyd-warshal 알고리즘 이용

• 플로이드 와샬 알고리즘

  • 모든 정점 => 모든 정점 최단 경로 구하기
  • d[i][j] = i부터 j까지의 최저 택시 요금
  • min(d[s][k]+d[k][a]+d[k][b])를 구하면 됨

• 다익스트라 알고리즘

  • 한 정점 => 모든 정점 최단 경로 구하기
  • 배열(dist)과 우선순위 큐(qp)를 이용해서 첫 정점부터 각 노드까지의 거리를 배열에 업데이트하는 방식
  • 우선순위 큐에 다음 갈 수 있는 노드들을 넣으면서 해당 거리를 dist 배열에서 갱신하는 방식
  • a, b 각각의 최단 거리 비용과 특정 지점까지의 최단 거리 비용 중 가장 작은 것을 반복문으로 추출

 

코드

코드는 모두 이곳을 참조함.

플로이드 와샬 알고리즘 이용

#include <string>
#include <vector>

using namespace std;

int graphMap[201][201];

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {

    for(int i=0; i<201; i++){
        for(int j=0; j<201; j++){
            graphMap[i][j] = 1e8;
            if(i==j)
                graphMap[i][j] = 0;
        }
    }

    for(int i=0; i<fares.size(); i++){
        graphMap[fares[i][0]][fares[i][1]] = fares[i][2];
        graphMap[fares[i][1]][fares[i][0]] = fares[i][2];
    }

    for(int i=0; i<=n; i++){
        for(int j=0; j<=n; j++){
            for(int k=0; k<=n; k++){
                graphMap[j][k] = min(graphMap[j][k], graphMap[j][i]+graphMap[i][k]);
            } 
        }
    }

    int answer = 1e9;

    for(int i=0; i<=n; i++){
        answer = min(answer, graphMap[s][i]+graphMap[i][a]+graphMap[i][b]);
    }

    return answer;
}