[C++]프로그래머스 배달 (다익스트라 알고리즘 이해)

코딩테스트 연습 - 배달 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

다익스트라 알고리즘은 처음이라..

23. 다익스트라(Dijkstra) 알고리즘 : 네이버 블로그 (naver.com)

23. 다익스트라(Dijkstra) 알고리즘

우선 다익스트라 알고리즘이란, 노드들이 있고 노드들간의간선에 각 가중치가 정해져 있을 때 최단거리를 구할 때 쓰는 알고리즘이다.

유명한 길찾기 알고리즘 중 하나임.

인공위성 등에 사용된다고 함.

처음이라 이해가 조금 어려웠다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<pair<int, int>> v[51];
vector<int> dist;
//다익스트라
void dijkstra()
{
    int pos;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;//우선순위큐에만 top()존재함.
    q.push({1, 0});
    while(!q.empty()){
        pos = q.top().first;
        q.pop();
        for(int i = 0; i<v[pos].size(); i++){
            if(dist[v[pos][i].first] > dist[pos] + v[pos][i].second){ //dist에 저장된 최소거리보다 새로 계산한 값이 더 최솟값이므로 이때만 새로운 연산 필요
                dist[v[pos][i].first] = dist[pos] + v[pos][i].second;
                q.push({v[pos][i].first, v[pos][i].second});
            }
        }
    }
}

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], c = road[i][2];
        v[a].push_back({b,c});
        v[b].push_back({a,c});
    }//초기화
    
    dist.resize(N + 1, 1e9); //resize : 배열 크기 재할당 함수
    dist[1] = 0; //1에서 i까지의 최소거리
    dijkstra();
    
    for(int i = 1; i < dist.size(); i++) if(dist[i] <= K) answer++;
    return answer;
}

1. 첫번째 : vector<pair<int, int>> v[51];을 초기화하라

    vector<pair<int, int>> v[51];
    
    for(int i = 0; i < road.size(); i++)
    {
        int a = road[i][0], b = road[i][1], c = road[i][2];
        v[a].push_back({b,c});
        v[b].push_back({a,c});
    }//초기화

이를 도표로 나타내면

0
1	{2, 1}	{4, 2}	. . .
2	{1, 1}	{3, 3}	{5, 2}	. . .
3	{2, 3}	{5, 1}	. . .
4	{1, 2}	{5, 2}	. . .
5	{2, 2}	{3, 1}	{4, 2}	. . .

이렇게 v[a]와 v[b]에는 각각 b,a가 pair의 first값에 들어간다. 이는 어떤 노드와 연결이 되었는가를 나타내는 값이다.

pair의 second에는 노드와 노드 사이의 간선 가중치값이 들어간다.

 

이렇게하면 초기화가 완료가 된다.

 

2.그 다음에는 최솟값을 담는 배열 dist을 resize함수를 이용해서 N + 1만큼 무한대(1e9)로 재할당해준다. (최댓값을 담아도 상관 없음)

우리는 노드 1에서부터 다른 노드까지의 최소길이를 구해야 하므로 dist[1] = 0이다.

 

3.다익스트라 알고리즘 함수를 시작한다. (여기서 참조되어야 하는 v배열과 dist배열은 전역변수로 선언되어야 함)

3-1.우선순위 큐 함수 선언

priority_queue<pair<int, int>> q;

이렇게 하면 내림차순이지만 오름차순으로 하고 싶으면 위와 같이 선언해야 함.

playground :: [C++] priority_queue (오름차순/내림차순 큐) (tistory.com)

[C++] priority_queue (오름차순/내림차순 큐)

-> 우선순위 큐 형식에 대한 설명

 

*우선순위 큐를 써야하는 이유?

1과 가까운 (작은 값) 노드부터 참조해야 queue 삽입과 삭제가 빈번하지 않게 됨

가장 작은 값이 항상 top으로 올라오는 구조이므로 우린 이것을 참조하면서 갈 수 있게 된다.

 

3-2.queue의 첫 번째 값 지정한 뒤 pop해주기

기본적으로 queue에는 v의 요소들의 first, second값이 queue의 first, second에 들어가지만 첫 값은 정해져있기 않기 때문에 정해줘야 함. 기본적으로 q.push({1, 0});

 

3-3.queue가 빌 때까지 while문 돌리기

처음 지정해준 값을 pos로 지정하여 시작한다. v 선언했을 때 각 노드마다 2차원배열에서 옆으로 늘어나는 방식으로 push해주며 연결되어있는 노드가 있다면 옆에 붙었다.

따라서 각 줄마다 그 줄의 길이만큼 for문으로 살피며 최솟값을 담는 배열이었던 dist[pos]가 새로 받은 최솟값보다 크면 새로운 최솟값이 더 작다는 뜻이므로 그때마다 dist값을 바꿔주고 다음 while문에서 그 다음 노드를 참조하도록 queue에 할당해주어야 하므로 해당하는 경우 push한다.

그리고 이를 반복한다.

 

* if문에 해당하는 경우에만 queue에 넣어주는 이유: 그렇지 않으면 이미 first의 최솟값이 성립한다는 의미이므로 굳이 다시 그 노드에 대해 최솟값을 찾아줄 필요가 없음

 

4.마지막은 쉽다. 그냥 경로까지의 최솟값과 K의 비교

이부분은 문제가 안 될거라고 생각한다. 

 

 

---

반복으로 익히자.