[프로그래머스] 배달 / 다익스트라 알고리즘

 

Level. 2

 

문제

N개의 마을로 이루어진 나라가 있습니다.
이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다.
각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다.
도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다.
각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다.
다음은 N = 5, K = 3인 경우의 예시입니다.

출처 : 프로그래머스

위 그림에서 1번 마을에 있는 음식점은 [1, 2, 4, 5] 번 마을까지는 3 이하의 시간에 배달할 수 있습니다.
그러나 3번 마을까지는 3시간 이내로 배달할 수 있는 경로가 없으므로 3번 마을에서는 주문을 받지 않습니다.
따라서 1번 마을에 있는 음식점이 배달 주문을 받을 수 있는 마을은 4개가 됩니다.
마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return 하도록 solution 함수를 완성해주세요.

* 제한사항
- 마을의 개수 N은 1 이상 50 이하의 자연수입니다.
- road의 길이(도로 정보의 개수)는 1 이상 2,000 이하입니다.
- road의 각 원소는 마을을 연결하고 있는 각 도로의 정보를 나타냅니다.
- road는 길이가 3인 배열이며, 순서대로 (a, b, c)를 나타냅니다.
   a, b(1 ≤ a, b ≤ N, a != b)는 도로가 연결하는 두 마을의 번호이며, c(1 ≤ c ≤ 10,000, c는 자연수)는 도로를 지나는데 걸리는 시간입니다.
   두 마을 a, b를 연결하는 도로는 여러 개가 있을 수 있습니다.
   한 도로의 정보가 여러 번 중복해서 주어지지 않습니다.
- K는 음식 배달이 가능한 시간을 나타내며, 1 이상 500,000 이하입니다.
- 임의의 두 마을간에 항상 이동 가능한 경로가 존재합니다.
- 1번 마을에 있는 음식점이 K 이하의 시간에 배달이 가능한 마을의 개수를 return 하면 됩니다.

 

 

풀이

#include <vector>
#include <queue>
#include <iostream>
using namespace std;


/*
마을의 개수 N
각 마을을 연결하는 도로의 정보 road
음식 배달이 가능한 시간 K
1번 마을에 있는 음식점이 K 이하의 시간에 배달이 가능한 마을의 개수를 리턴
>> 다익스트라 알고리즘

c++의 우선순위 큐는 Max Heap설정되어있다.
여기서는 우선순위 큐를 Min Heap으로 사용하였다. 
*/

vector<pair<int, int>> v[51]; // 마을들의 양방향 간선 벡터 저장
vector<int> dist; // 각 마을마다 최단거리 기록

void dijkstra(){
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pq; // Min Heap
    //최소힙을 구하는 연산을 통해서 최소비용이 드는 정점들부터 처리
    pq.push({1,0}); // 초기값. 1부터 시작한다. 
    
    while(!pq.empty()){
        int cur = pq.top().first; // 현재위치
        int cost = pq.top().second; // 이동거리
        pq.pop();
        
        if(dist[cur] < cost) continue;
        
        for(int i=0; i<v[cur].size(); i++){ // 현재 cur와 연결된 모든 노드들과의 거리를 비교한다. 
            int next = v[cur][i].first; // 다음 큐의 노드 위치
            int ncost = v[cur][i].second; // 다음 큐의 노드 이동거리
            if(dist[next] > dist[cur] + ncost){ // 최소 이동거리 갱신
                dist[next] = dist[cur] + ncost;
                pq.push({next, ncost});
            }
        }
 
    }
}

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;
    dist.resize(N+1, 2e9); // 처음에 무한대로 초기화. 2e9 = 2000000000
    
    for(int i=0; i<road.size(); i++){
        int s = road[i][0];
        int e = road[i][1];
        int cost = road[i][2];
        
        v[s].push_back({e, cost});
        v[e].push_back({s, cost});
    }
    
    dist[1] = 0; // 1에서 1까지 거리 0
    dijkstra();
    
    for(int i=1; i<dist.size(); i++){
        if(dist[i] <= K) answer += 1;
    }
    
    return answer;
}

 

 

그래프의 최단 경로 탐색

• BFS : 가중치가 없는 그래프의 최단경로를 찾는 경우 사용할 수 있다. 
• 다익스트라 : 그래프에 가중치가 있을 때 사용할 수 있다. 단, 음수간선이 없을 때 사용한다. 

다익스트라 알고리즘 동작단계

1. 출발노드와 도착노드를 설정한다.
2. 최단 거리를 저장할 데이터를 무한대(INF)로 초기화한다.
3. 시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교하여 업데이트시킨다. 
4. 방문한 정점들 중 가장 가중치 값이 작은 정점을 방문한다. 
5. 해당 정점을 거쳐서 갈 수 있는 정점의 거리가 현재 기록된 값보다 작다면, 해당 값을 갱신한다. 
6. 4~5의 과정을 반복한다. 

필요한 데이터

1. disk : 각 정점까지 가는데 드는 최소비용을 저장할 데이터. 초기값을 무한대로 설정
2. v : 마을들의 양방향 그래프
3. pq : 우선순위큐. 기본 Max heap이지만 여기선 작은 값이 우선이 되는 Min heap 우선순위 큐를 사용한다
          최소비용이 드는 정점부터 처리하기 위함이다.  

 

Priority Queue & Pair

priority_queue<pair<int, int>> pq; // Max Heap
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pq; // Min Heap

• 기본적 사용 (내림차순)
  -> 첫 번째 인자 기준으로 내림차순 정렬. 같다면 두 번째 인자를 기준으로 내림차순 정렬한다.
• greater함수 사용 (오름차순)
  -> 첫 번째 인자 기준으로 오름차순 정렬. 같다면 두 번째 인자 기준으로 오름차순 정렬한다. 

 

 

---

다른 풀이

#include <iostream>
#include <vector>

using namespace std;

int     hour[51][51] = { 0, };
bool    possible[51] = { 0, };

void    recurs(int before, int t, int K, bool *visit)
{
    if (t > K)
        return ;
    possible[before] = true;
    for (int i = 2; i < 51; i++)
    {
        if (!visit[i] && hour[before][i])
        {
            visit[i]= true;
            recurs(i, t + hour[before][i], K, visit);
            visit[i] = false;
        }
    }
}

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;

    for (int i = 0; i < road.size(); i++)
    {
        int a = road[i][0], b = road[i][1], t = road[i][2];
        if (t < hour[a][b] || hour[a][b] == 0)
        {
            hour[a][b] = t;
            hour[b][a] = t;
        }
    }
    bool    visit[51] = { 0, };
    visit[1] = true;
    recurs(1, 0, K, visit);
    for (int i = 1; i < 51; i++)
    {
        if (possible[i] == true)
            answer++;
    }

    return answer;
}

 

---

https://school.programmers.co.kr/learn/courses/30/lessons/12978?language=cpp 

프로그래머스

https://ongveloper.tistory.com/61

프로그래머스 배달 c++ (다익스트라)

https://www.acmicpc.net/board/view/19996

글 읽기 - 2e9 가 무엇을 의미하나요??

https://chanhuiseok.github.io/posts/algo-54/

알고리즘 - c++의 priority_queue 사용법

https://yabmoons.tistory.com/633

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

https://yabmoons.tistory.com/364

[ 다익스트라 알고리즘 ] 개념과 구현방법 (C++)

https://velog.io/@kasterra/%ED%95%B5%EC%8B%AC-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%9E%98%ED%94%84-%EC%B5%9C%EB%8B%A8-%EA%B2%BD%EB%A1%9C-%ED%83%90%EC%83%89