[Algorithm] Programmers :: 합승 택시 요금

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

프로그래머스

 

#include <string>
#include <vector>
#include <memory.h>
using namespace std;
 
const int MAX = 0x3f3f3f3f;
 
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
 
    int graph[201][201] = { 0 };
    memset(graph, 0x3f, sizeof(graph));
 
    for (int i = 1; i <= n; i++)
    {
        graph[i][i] = 0;
    }
 
    for (int i = 0; i < fares.size(); i++)
    {
        graph[fares[i][0]][fares[i][1]] = fares[i][2];
        graph[fares[i][1]][fares[i][0]] = fares[i][2];
    }
 
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            if (graph[i][k] != 0x3f3f3f3f)
            {
                for (int j = 1; j <= n; j++)
                {
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
                }
            }
        }
    }
 
    int minCost = MAX;
    long long cost = 0;
 
    for (int i = 1; i <= n; i++)
    {
        cost = (long long)graph[s][i] + graph[i][a] + graph[i][b];
        minCost = min<long long>(minCost, cost);
    }
 
    return minCost;
}

 

카카오 3레벨짜리 문제다. 위 코드는 플로이드와샬로 해결한 문제다.

플로이드와샬을 모른 상태에서 문제를 봤을때는 어떤식으로 해야할지 몰랐다가, 플로이드와샬 기본예제 문제 하나 푸니까 바로 풀 수 있었던 문제다. 사실 밑에 후술하겠지만, 다익스트라로도 풀 수 있는 문제다.(이게 더 효율이좋다)

일단 이 문제같은 경우는 플로이드와샬로 해도 효율성테스트에서 안걸리고 무사히 통과가 된다.

 

3중포문에서 세번째 포문에 들어가기 직전에 if (graph[i][k] != 0x3f3f3f3f) 을 해주는 이유는, 어차피 graph[i][k]값이 INF값이면 graph[k][j]는 값이 최소 0이상이기 때문에 graph[i][j]에는 자기자신 graph[i][j]가 그대로 들어간다.그래서 굳이 실행시켜줄 필요가 없는것이다. min함수의 좌항인 graph[i][j]의 '최대값'은 INF이고, 우항인 graph[i][k] + graph[k][j] 의 '최소값'은 INF다. 그러니 비교가 무의미하다. ( if문 안걸어놔도 pass가 뜨기는 한다.)

 

 

뭔가 전형적인 플로이드와샬문제 같지만, 사실 다익스트라로 더 효율성 좋게 해결이 가능하다.

왜냐하면 이 문제같은 경우, '자신을 제외한 다른 노드까지의 최단거리'를 알아내야하는 정점은 딱 3개이기 때문이다.

문제의 n이(정점이) 10개든 100개든, 우리가 필요한 '다른 노드까지의 최단거리가 업데이트 되어있는 정점'은 3개다.

바로 출발정점,A의 도착정점, B의 도착정점이다. (문제에서는 매개변수인 s,a,b이다.)

나머지는 알 필요없다. 이거 3개만 구하고, 위의 코드마지막부분처럼 각 정점돌면서 's에서 해당정점까지의 거리' + 'a에서

해당정점까지의 거리' + 'b에서 해당정점까지의 거리'를 더한값 중, 제일 작게 나온 값을 리턴하면 된다.

이게 가능한 이유는, 양방향간선이기 때문이다. 양방향간선이기 때문에 a에서 다익을 수행할경우, 

a에서 다른정점까지의 최단거리 == 다른정점에서 a까지의 최단거리 가 성립하기 때문이다.

 

아래는 다익스트라를 사용한 코드다.

#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <memory.h>
using namespace std;
 
const int MAX = 0x3f3f3f3f;
 
struct Node
{
    int node;
    int dist;
 
    Node() {};
    Node(int _node, int _dist) : node(_node), dist(_dist) {};
};
 
struct cmp
{
    bool operator()(const Node& a, const Node& b) // for minHeap
    {
        return a.dist > b.dist;
    }
};
 
void dij(int startVertex, int distIndex, vector<vector<Node>>& graph, vector<vector<int>>& distMap)
{
    distMap[distIndex][startVertex] = 0;
    priority_queue<Node, vector<Node>, cmp> pq;
    pq.push(Node(startVertex, 0));
 
    while (!pq.empty())
    {
        Node popedNode = pq.top();
        pq.pop();
 
        int curNode = popedNode.node;
        int curDist = popedNode.dist;
 
        if(curDist > distMap[distIndex][curNode]) continue;
        
        for (int i = 0; i < graph[curNode].size(); i++)
        {
            int nextNode = graph[curNode][i].node;
            int nextDist = graph[curNode][i].dist;
 
            if (curDist + nextDist <= distMap[distIndex][nextNode])
            {
                distMap[distIndex][nextNode] = curDist + nextDist;
                pq.push(Node(nextNode, curDist + nextDist));
            }
        }
    }
}
 
int solution(int n, int s, int a, int b, vector<vector<int>> fares) 
{
    vector<vector<Node>> graph(201);
    vector<vector<int>> distMap(3, vector<int>(201,0x3f3f3f3f));
 
    for (int i = 0; i < fares.size(); i++)
    {
        graph[fares[i][0]].push_back(Node(fares[i][1], fares[i][2]));
        graph[fares[i][1]].push_back(Node(fares[i][0], fares[i][2]));
    }
 
    dij(s, 0, graph, distMap); // s정점 -> 다른정점간의 최단거리 업데이트.
    dij(a, 1, graph, distMap); // a정점 -> 다른정점간의 최단거리 업데이트.
    dij(b, 2, graph, distMap); // b정점 -> 다른정점간의 최단거리 업데이트.
 
    long long minCost = 0x3f3f3f3f;
 
    for (int i = 1; i <= n; i++)
    {
        minCost = min<long long>(minCost, (long long)distMap[0][i] + distMap[1][i] + distMap[2][i]);
    }
 
    return minCost;
}