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

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

 

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

프로그래머스

---

 

해결전략

 

Dijkstra  다익스트라 알고리즘 (최단경로 알고리즘)

 

다익스트라(Dijkstra) 알고리즘은 그래프에서 한 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘이다. 

이 알고리즘은 가중치가 음수인 간선이 없는 그래프에서만 사용할 수 있\다.

 

다익스트라 알고리즘

1. 출발 노드를 설정
   • pQ.push(Edge(1,0))
2. 출발 노드를 기준으로 그래프의 모든 노드의 비용을 초기화 (출발 노드의 경우 0, 나머지 노드는 무한대)
   • vector<int> dist(n + 1, 2147000000);
   • dist[1] = 0; 
3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택
   
   • if (dist[curLoc] < curCost) continue; 
   • if (dist[nextLoc] > nextCost) 
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최소 비용을 갱신
   
   • dist[nextLoc] = nextCost;
     pQ.push(Edge(nextLoc, nextCost));
5. 위 과정을 반복합니다.

---

 

정답 코드

 

#include <vector>
#include <queue>
using namespace std;
 
// Edge 구조체 정의. 각 도시와 그 도시로 가는데 드는 비용을 저장한다.
struct Edge{
    int city;
    int cost;
    Edge(int a, int b) {
        city = a;
        cost = b;
    }
    // 우선순위 큐에서 비용이 적은 도시부터 뽑기 위해 연산자를 오버로딩한다. 비용이 적은 도시가 더 높은 우선순위를 가지도록 정의합니다.
    bool operator<(const Edge& e) const{
        return cost > e.cost;
    }
};
 
int solution(int n, vector<vector<int> > road, int k) {
  
    vector<int> dist(n + 1, 2147000000); // dist 벡터를 생성하고, 모든 도시로 가는 비용을 무한대로 초기화
   
    priority_queue<Edge> pQ;  // 우선순위 큐를 생성
    
    pQ.push(Edge(1,0)); // 1번 도시에서 출발하므로, 1번 도시 자신으로 가는 비용은 0이다.
    dist[1] = 0; // 1번 도시는 자기자신이므로 비용 0
 
    while (!pQ.empty())
    {
        // 큐에서 비용이 가장 적은 도시를 뽑습니다. 이 도시가 바로 현재 위치입니다.
        int curLoc = pQ.top().city;
        int curCost = pQ.top().cost;
        pQ.pop();
 
        // 이미 구한 도시까지의 최소비용이 현재 비용보다 작으면, 이 도시로 가는 다른 경로를 무시한다.
        if (dist[curLoc] < curCost) continue;
 
       
        for (int i = 0; i < road.size(); i++) // 모든 도로를 확인
        {          
            if (road[i][0] == curLoc || road[i][1] == curLoc) // 현재 도시와 연결된 도로를 찾는다.
            {
                // 연결된 도시와 그 도시까지 가는 비용을 계산한다.
                int nextLoc = road[i][0] == curLoc ? road[i][1] : road[i][0]; // 도로는 양방향
                int nextCost = curCost + road[i][2];
				
                // 만약 새로 구한 비용이 기존의 비용보다 작다면, 비용을 갱신하고 큐에 넣는다.
                // 이는 다익스트라 알고리즘에서 최소 비용을 갱신하는 부분에 해당한다.
                if (dist[nextLoc] > nextCost) 
                {
                    dist[nextLoc] = nextCost;
                    pQ.push(Edge(nextLoc, nextCost));
                }
            }
        }
    }
 
    int answer = 0; // k 이하의 비용으로 갈 수 있는 도시의 수
    for (int i = 1; i < dist.size(); i++) // 모든 도시를 순회하며, k 이하의 비용으로 갈 수 있는 도시의 수를 센다.
    {
        if (dist[i] <= k) answer++;
    }
 
    return answer;
}

 

 

---