[프로그래머스] 배달

배달(https://programmers.co.kr/learn/courses/30/lessons/12978)

---

1. 이해하기

• 각 마을은 양방향으로 통행할 수 있는 도로가 있다.
• 각 도로를 지날 때 걸리는 시간은 도로별로 다르다.
• 배달은 1번 마을에 있는 음식점에서 각 마을로 음식배달을 한다.
• K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 한다.
• 최단거리 문제.

---

2. 구현하기

• 1번에서 시작하는 다익스트라 구현을 통해서 각 마을마다 최단거리를 구한다.

  • Python

    • dijkstra(road,N): 우선순위 큐를 이용해서 다익스트라를 구현한다. 어느 지점과 이어져있는지를 알기 위하여 road를 받고 각 마을마다 거리를 초기화하기 위해서 N을 받는다. 이후 반복문을 이용하여 각 지점의 최단거리를 갱신해준다.

    def dijkstra(road,N):
        INF = 987654321
        dist = [INF for i in range(N+1)]
        road.sort()
        pq = PriorityQueue()
        pq.put([0,1])
        dist[1] = 0
        while not pq.empty():
            cost,here = pq.get()
            if cost > dist[here]: continue
            for i in range(len(road)):
                if road[i][0] == here:
                    there,nextCost = road[i][1], road[i][2]+cost
                    if nextCost < dist[there]:
                        dist[there] = nextCost
                        pq.put([nextCost,there])
                elif road[i][1] == here:
                    there,nextCost = road[i][0], road[i][2]+cost
                    if nextCost < dist[there]:
                        dist[there] = nextCost
                        pq.put([nextCost,there])
        return dist

  • C++

    • dijkstra(N): 각 마을의 거리를 초기화해주기 위하여 N을 받는다. 이후에는 인접리스트를 이용해 각 마을의 최단거리를 갱신해준다. 이때 우선순위큐를 이용한다.

    void dijkstra(int N) {
        for(int i = 1; i <= N; i++) dist[i] = INF;
        priority_queue<pair<int,int>> pq;
        pq.push({0,1});
        dist[1] = 0;
        while(!pq.empty()) {
            int cost = -pq.top().first, here = pq.top().second;
            pq.pop();
            if(cost > dist[here]) continue;
            for(int i = 0; i < adj[here].size(); i++) {
                int there = adj[here][i].first;
                int nextCost = adj[here][i].second+cost;
                if(nextCost < dist[there]) {
                    dist[there] = nextCost;
                    pq.push({-nextCost,there});
                }
            }
        }
    }

---

3. 전체코드

• Python

  from queue import PriorityQueue
  
  def dijkstra(road,N):
      INF = 987654321
      dist = [INF for i in range(N+1)]
      road.sort()
      pq = PriorityQueue()
      pq.put([0,1])
      dist[1] = 0
      while not pq.empty():
          cost,here = pq.get()
          if cost > dist[here]: continue
          for i in range(len(road)):
              if road[i][0] == here:
                  there,nextCost = road[i][1], road[i][2]+cost
                  if nextCost < dist[there]:
                      dist[there] = nextCost
                      pq.put([nextCost,there])
              elif road[i][1] == here:
                  there,nextCost = road[i][0], road[i][2]+cost
                  if nextCost < dist[there]:
                      dist[there] = nextCost
                      pq.put([nextCost,there])
      return dist
  
  def solution(N, road, K):
      answer = 0
      dist = dijkstra(road,N)
      for d in dist:
          if d <= K:
              answer+=1
      return answer

• C++

  #include <iostream>
  #include <vector>
  #include <queue>
  using namespace std;
  
  vector<pair<int,int>> adj[51];
  int dist[51];
  const int INF = 987654321;
  
  void dijkstra(int N) {
      for(int i = 1; i <= N; i++) dist[i] = INF;
      priority_queue<pair<int,int>> pq;
      pq.push({0,1});
      dist[1] = 0;
      while(!pq.empty()) {
          int cost = -pq.top().first, here = pq.top().second;
          pq.pop();
          if(cost > dist[here]) continue;
          for(int i = 0; i < adj[here].size(); i++) {
              int there = adj[here][i].first;
              int nextCost = adj[here][i].second+cost;
              if(nextCost < dist[there]) {
                  dist[there] = nextCost;
                  pq.push({-nextCost,there});
              }
          }
      }
  }
  
  int solution(int N, vector<vector<int> > road, int K) {
      int answer = 0;
      for(int i = 0; i < road.size(); i++) {
          int u = road[i][0], v = road[i][1], cost = road[i][2];
          adj[u].push_back({v,cost});
          adj[v].push_back({u,cost});
      }
      dijkstra(N);
      for(int i = 1; i <= N; i++)
          if(dist[i] <= K)
              answer++;
  
      return answer;
  }

---

4. 배운점

• 파이썬에서 우선순위큐를 사용하려면 from queue import PriotiryQueue를 해야한다.
• pq.put()을 이용해서 큐에 넣고 pq.get()을 통해서 가장 앞에 있는 값을 가져오면서 뺀다.