Level 2. 배달

Level 2. 배달

 

 

처음에 그냥 DFS로 해결하려다가 방문 여부를 관리하면서 최소 비용을 갱신하는 방법이 잘 떠오르지 않아 찾아봤다.

 

결국은 전형적인 다익스트라 알고리즘 문제였다..

 

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

 

vector를 활용한 인접 리스트로 그래프를 만들었다.

 

처음에 우선순위 큐에 시작점을 0의 비용으로 넣고, 매번 가장 비용이 적은 정점을 우선순위 큐에서 뽑는다.

 

뽑은 정점의 인접 정점들의 비용을 갱신한다.

• 인접 정점의 비용 > 나의 비용 + 간선 거리

 

비용이 음수인 정점이 없으므로, 루프가 발생하면 항상 비용이 증가해 알아서 멈추게 된다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

#define UNREACHABLE INT_MAX

using namespace std;

typedef struct Edge
{
    union { int to;     int v; };
    union { int dist;   int cost; };

    friend bool operator < (const Info& A, const Info& B) { return A.cost < B.cost; }
} Info;

void Dijkstra(vector<vector<Edge>>& dist, vector<int>& cost)
{
    queue<Info> que;

    que.emplace(Info {1, 0});
    cost[1] = 0;

    while (!que.empty())
    {
        Info i = que.top(); que.pop();

        for (Edge& adj : dist[i.v])
        {
            if (cost[adj.to] > i.cost + adj.dist)
            {
                cost[adj.to] = i.cost + adj.dist;
                que.emplace(Edge {adj.to , cost[adj.to]});
            }
        }
    }
}

int solution(int N, vector<vector<int>> road, int K)
{
    int answer = 1;
    vector<vector<Edge>> dist(N + 1);
    vector<int> cost(N + 1, UNREACHABLE);

    for (vector<int>& rd : road)
    {
        dist[rd[0]].emplace_back(Edge {rd[1], rd[2]});
        dist[rd[1]].emplace_back(Edge {rd[0], rd[2]});
    }

    Dijkstra(dist, cost);

    for (int i = 2; i <= N; ++i)
        answer += (cost[i] <= K);

    return answer;
}