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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12978

코딩테스트 연습 - 배달

 

다익스트라 알고리즘을 알고있으면 별 고민을 하지 않고 풀 수 있는 문제다.

 

문제 풀이는 다음과 같다.

 

1. 필요한 변수들을 선언하고 값을 저장해준다.

vector<pair<int,int>> v[51]; // (1)
vector<int> dist;

...

int solution(int N, vector<vector<int>> road, int K) {
    int answer = 0;
    dist.resize(N+1, 1e9); // (2)
    for(int i=0; i<road.size(); i++){ // (3)
        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});
    }
...

(1) 먼저 마을들의 양방향 간선 벡터와 각 마을의 최소 거리를 저장해줄 벡터를 선언한다.

(2) 전역변수로 설정한뒤 resizing을 해준다. 배열의 초기값은 1e9으로 해줬는데, K의 최대값을 초과한 500,001으로 해줘도 무방하다.

(3) road의 사이즈만큼 for문을 돌려 양방향 간선의 값들을 모두 저장해준다.

 

2. 무조건 출발은 1번 노트부터 시작해준다. 때문에 dist[1] = 0으로 코드를 작성해준뒤, dijkstra 함수를 실행한다.

    dist[1] = 0;
    dijkstra(K); // 매개변수가 K인 이유는 최대값 K와 이동거리를 비교하기 위함

 

3. 다음은 dijkstra 함수의 내부이다.

void dijkstra(int K){
    int pos, dis, next, ndis; // 1
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q; // 2
    q.push({1,0}); // 3
    while(!q.empty()){
        pos = q.top().first;
        dis = q.top().second;
        q.pop();
        for(int i=0; i<v[pos].size(); i++){
            next = v[pos][i].first;
            ndis = v[pos][i].second;
            if(dist[next]>dist[pos]+ndis){
                dist[next] = dist[pos]+ndis;
                q.push({next,ndis});
            }
        }
    }
}

(1) 필요한 함수들을 미리 선언한다. pos는 현재 노드의 위치, dis는 현재 노드의 이동거리 값, next는 다음 노드의 위치, ndis는 다음 노드의 이동 거리 값이다.

(2) 우선순위 큐를 선언한다. 지금 이 문제는 다익스트라로 접근하고 있으며, 다익스트라에서는 큐가 아닌 우선순위 큐가 이용되어야한다.

만약 우선순위 큐를 사용하지 않고 일반 큐를 사용할 경우, 무조건 시간초과가 발생한다. 

우리는 우선순위 큐를 활용해서 불필요한 계산들을 반복하지 않을 수 있다.

또한 최단 거리를 구하는 것이 목적이므로, 우선순위큐는 오름차순으로 정렬해준다.

* 이 외에 굳이 오름차순으로 정렬하지 않아도 값을 -로 값을 저장해주어 비교하는 방법도 있는데, 본인이 편한 방법으로 접근하면 된다.

(3) 큐에 현재 노드의 위치값과 이동거리인 {1,0}을 삽입해준다.

 

4. while문을 천천히 봐보자.

void dijkstra(int K){
    int pos, dis, next, ndis;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
    q.push({1,0});
    while(!q.empty()){
        pos = q.top().first; // 1
        dis = q.top().second;
        q.pop();
        for(int i=0; i<v[pos].size(); i++){ // 2
            next = v[pos][i].first; // 3
            ndis = v[pos][i].second;
            if(dist[next]>dist[pos]+ndis){ // 4
                dist[next] = dist[pos]+ndis; // 5
                q.push({next,ndis});
            }
        }
    }
}

(1) pos에 큐의 현재 노드 위치, dis에 큐의 현재 노드의 이동 거리를 저장해준뒤 pop시켜준다.

(2) 현재 노드의 v벡터 사이즈만큼 for문을 돌린다. 이 말은 즉슨, 현재 pos와 연결된 모든 노드들과의 거리를 비교한다는 뜻이다.

(3) next에 다음 큐의 노드 위치, ndis에 다음 큐의 노드 이동 거리를 저장해준다.

(4) 만약 dist[next] > dist[pos]+nids일 경우, 이말은 즉슨, 아래와 같을 경우,

다음 노드의 누적 이동 거리 > 현재 노드의 누적 이동거리 + 다음 노드의 이동거리

다음 노드의 누적 이동거리는 현재 노드의 누적 이동 거리 + 다음 노드의 이동 거리로 저장해준다. 그리고 큐에 다음 위치와 다음 위치의 이동 거리를 삽입해준다.

여기서 포인트는, dist[pos]를 사용했다는 점이다. 왜 dis는 안되고 dist[pos]만 되는걸까?

이는 dist[pos]를 통해서 갱신되는 최소 이동거리를 활용할 수 있기 때문이다.

 

5. while문을 빠져나와 main으로 회귀하고, 여탯껏 저장한 최소 누적 이동값들 중 K이하의 갯수만큼 answer값을 증가시켜준다.

for(int i=1; i<dist.size(); i++) if(dist[i]<=K) answer++;

 

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

vector<pair<int,int>> v[51];
vector<int> dist;

void dijkstra(int K){
    int pos, dis, next, ndis;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
    q.push({1,0});
    while(!q.empty()){
        pos = q.top().first;
        dis = q.top().second;
        q.pop();
        for(int i=0; i<v[pos].size(); i++){
            next = v[pos][i].first;
            ndis = v[pos][i].second;
            if(dist[next]>dist[pos]+ndis){
                dist[next] = dist[pos]+ndis;
                q.push({next,ndis});
            }
        }
    }
}

int solution(int N, vector<vector<int>> road, int K) {
    int answer = 0;
    dist.resize(N+1, 1e9);
    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[1] = 0;
    dijkstra(K);
    for(int i=1; i<dist.size(); i++) if(dist[i]<=K) answer++;
    return answer;
}

 

정확성 테스트

테스트 1 〉	통과 (0.01ms, 3.97MB)
테스트 2 〉	통과 (0.01ms, 3.89MB)
테스트 3 〉	통과 (0.01ms, 3.68MB)
테스트 4 〉	통과 (0.01ms, 3.97MB)
테스트 5 〉	통과 (0.02ms, 3.94MB)
테스트 6 〉	통과 (0.01ms, 3.97MB)
테스트 7 〉	통과 (0.01ms, 3.7MB)
테스트 8 〉	통과 (0.01ms, 3.96MB)
테스트 9 〉	통과 (0.01ms, 3.93MB)
테스트 10 〉	통과 (0.02ms, 3.91MB)
테스트 11 〉	통과 (0.01ms, 3.95MB)
테스트 12 〉	통과 (0.02ms, 3.94MB)
테스트 13 〉	통과 (0.02ms, 3.98MB)
테스트 14 〉	통과 (0.13ms, 3.93MB)
테스트 15 〉	통과 (0.17ms, 3.73MB)
테스트 16 〉	통과 (0.01ms, 3.98MB)
테스트 17 〉	통과 (0.01ms, 3.95MB)
테스트 18 〉	통과 (0.07ms, 3.98MB)
테스트 19 〉	통과 (0.18ms, 3.95MB)
테스트 20 〉	통과 (0.05ms, 3.94MB)
테스트 21 〉	통과 (0.21ms, 3.9MB)
테스트 22 〉	통과 (0.08ms, 3.97MB)
테스트 23 〉	통과 (0.20ms, 3.98MB)
테스트 24 〉	통과 (0.16ms, 3.96MB)
테스트 25 〉	통과 (0.26ms, 3.97MB)
테스트 26 〉	통과 (0.26ms, 3.98MB)
테스트 27 〉	통과 (0.25ms, 3.98MB)
테스트 28 〉	통과 (0.25ms, 4.02MB)
테스트 29 〉	통과 (0.27ms, 3.91MB)
테스트 30 〉	통과 (0.22ms, 3.99MB)
테스트 31 〉	통과 (0.02ms, 3.96MB)
테스트 32 〉	통과 (0.02ms, 3.99MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0