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

문제 링크

코딩테스트 연습 - 배달

 

 

 

풀이

자신의 점에서 모든 점까지의 최소 거리를 구하는 "다익스트라"문제다.

우선순위 큐를 이용해 풀었다.

 

우선순위 큐의 정렬방식이 디폴트로 오름차순으로 먼저 나오는 것이 최소값이지만 pair의 first로 기준하여 정렬하기 때문에 second에 cost(weight)값을 기준으로 정렬하기 위해서 struct cmp 구조체에서 () 연산자를 오버로딩(?)한다.

 

순서는 1) 초기화, 2) 다익스트라 로 진행한다.

1) 초기화

vector 컨테이너 Array를 선언하여 양방향을 이어준다.

 

2) 다익스트라

dist[] 배열은 1번 정점으로부터 최소 거리를 나타내는 배열인데 dist[1] = 0으로 자신의 정점의 최소 거리는 0의 값을 넣어주고 우선순위 큐(pq)에 1번 정점과 cost(weight)를 push하고 반복문을 시작한다.

반복분(pq에 원소가 없을 때까지)

{

    현재 정점(cur)과 현재 정점까지 온 비용(cost)를 pop()한다.

    만약 이미 dist에 저장된 것보다 크다면 continue;로 불필요한 연산은 없애준다.

    그리고 현재 정점(cur)과 연결된 정점(next)와 next까지 간 비용을 구한다.

    그 비용을 이미 dist[]에 저장된 next까지 비용과 비교하여 pq에 push

}

 

마지막 dist[]를 순회하며 K값보다 작은 비용을 answer 개수로 리턴

 

참고로 한 정점으로부터 모든 정점까지 최소 거리를 구하는 것이 아닌 모든 정점에서 모든 정점의 최소 거리를 구할 때는 플로이드 와샬(Floyd Warshall) 알고리즘을 사용한다.

 

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

using namespace std;

struct cmp{
  bool operator()(pair<int, int> p1, pair<int, int> p2){
      return p1.second > p2.second;
  }  
};

// 마을 개수 N, 제한 시간 K
int solution(int N, vector<vector<int>> road, int K) {
    int answer = 0;
    const int INF = 99999999;
    vector<int> dist(N+1, INF);          // 최소 거리
    vector<pair<int, int>> adj[N+1];           // 인접 리스트
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;      // 우선순위 큐 사용
    
    // init
    for(int i=0; i<road.size(); i++){
        int r = road[i][0];
        int c = road[i][1];
        int w = road[i][2];
        
        // 양방향
        adj[r].push_back(make_pair(c, w));
        adj[c].push_back(make_pair(r, w));
    }
    
    // 다익스트라
    dist[1] = 0;
    pq.push(make_pair(1, 0));
    while(!pq.empty()){
        int cur = pq.top().first;
        int cost = pq.top().second;     // 시작 정점부터 cur까지 오는데 비용
        // printf("cost(%d)\n", cost);
        pq.pop();
        // printf("cur(%d)\n", cur);
        if(dist[cur] < cost) continue;          // 지금 꺼낸 것보다 더 짧은 것이 저장돼있다.
        
        // 인접한 정점들 검사
        for(int i=0; i<adj[cur].size(); i++){
            int next = adj[cur][i].first;
            int nextCost = cost + adj[cur][i].second;
            // printf("next(%d)\n", next);
            // next를 거쳐서 간 비용이 더 적다면 갱신
            if(nextCost < dist[next]){
                dist[next] = nextCost;
                pq.push(make_pair(next, nextCost));
            }
        }
    }
    
    // K보다 작은 비용들 저장
    for(int i=0; i<dist.size(); i++){
        if(dist[i] <= K) answer++;
    }
    
    return answer;          // 1번 마을에서 K 이하 시간으로 배달 가능한 마을 개수
}