[ 프로그래머스 배달 (Lv2) ] (C++)

프로그래머스의 배달(Lv2) 문제이다.

 

[ 문제풀이 ]

1번마을에서 K시간내에 배달을 갈 수 있는 마을의 갯수를 구해야 하는 문제이다.

 

#1. 구해야 하는 값

1번 마을에서 K시간내에 배달을 갈 수 있는 마을들이 몇 개가 있는지를 구해야 한다.

그리고 이를 위해서 문제에서 맵이 하나 주어지게 된다. 그렇다면 K 시간내에 배달을 가게 하기 위해서는 무조건 최단거리로 움직여 주는 것이 좋다. 예를 들어서 1번 마을에서 X번 마을까지 다이렉트로 가게 될 경우 10시간이 걸리는데, 다른 마을을 경유해서 가게 될 경우 4시간이 걸린다면 4시간을 선택하는 것이 더 좋다는 것이다.

즉 ! 우리는 1번 정점에서 다른 정점들 까지 가는데 걸리는 최단경로를 구해주면 된다.

최단경로를 구하는 방법에는 대표적으로 크게 3가지 알고리즘이 있다.

1. 다익스트라 알고리즘

2. 벨만포드 알고리즘

3. 플로이드 워샬 알고리즘

위와 같이 3가지 알고리즘이 있는데, 벨만포드 알고리즘 같은 경우에는 경로의 길이가 음수일 경우에 사용하면 유리한 알고리즘이지만, 이 문제에서는 걸리는 시간이 1이상이라고 했으므로 굳이 벨만포드 알고리즘을 사용할 필요는 없을 것 같다.

플로이드 워샬 알고리즘 같은 경우에는 하나의 특정한 정점에서 다른 정점까지의 최단경로는 물론, 모든 정점간의 최단경로를 구할 수 있는 알고리즘이다.

그런데 이 문제에서는 모든 정점간의 최단경로를 구할 필요 없이, 1번 정점과 나머지 정점들에 대한 최단경로만 구하면 되기 때문에 본인은 다익스트라 알고리즘을 이용해서 구현해 주었다.

물론 ! 주어지는 N 값이 최대 50이기 때문에 플로이드 워샬을 이용해서 구현을 하더라도 무방할 것이다.

아직 다익스트라 알고리즘에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ 다익스트라 알고리즘 알아보기(Click) ]

 

다익스트라 알고리즘을 이용해서 1번 정점과의 최단시간을 구했다면, 이 값을 이용해서 K시간 내에 있는 마을의 갯수가 몇 개인지만 카운트 해주면 된다.

 

[ 소스코드 ]

#include <vector>
#include <queue>
using namespace std;
 
vector<pair<int,int>> V[55];
vector<int> Dist;
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Dijkstra(int N)
{
    priority_queue<pair<int, int>> PQ;
    PQ.push(make_pair(0, 1));
    Dist[1] = 0;
 
    while (PQ.empty() == 0)
    {
        int Cost = -PQ.top().first;
        int Cur = PQ.top().second;
        PQ.pop();
 
        for (int i = 0; i < V[Cur].size(); i++)
        {
            int Next = V[Cur][i].first;
            int nCost = V[Cur][i].second;
 
            if (Dist[Next] > Cost + nCost)
            {
                Dist[Next] = Cost + nCost;
                PQ.push(make_pair(-Dist[Next], Next));
            }
        }
    }
}
 
int solution(int N, vector<vector<int> > road, int K)
{
    Dist.resize(N + 1, 2e9);
    for (int i = 0; i < road.size(); i++)
    {
        int N1 = road[i][0];
        int N2 = road[i][1];
        int Dist = road[i][2];
 
        V[N1].push_back(make_pair(N2, Dist));
        V[N2].push_back(make_pair(N1, Dist));
    }
 
    Dijkstra(N);
    int answer = 0;
    for (int i = 1; i <= N; i++)
    {
        if (Dist[i] <= K) answer++;
    }
 
    return answer;
}