[programmers] 부대복귀

https://school.programmers.co.kr/learn/courses/30/lessons/132266

프로그래머스

 

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

다익스트라 알고리즘.(shortest path problem)

 

---------------------------------------------------풀이----------------------------------------------------

 

#include <string>
#include <vector>
#include <queue>
#include <limits.h>

using namespace std;

vector<int> roads[500'001];
int N;
int dist[500'001] = {0, };  // 최소 거리

void init_dist(){
    for(int i = 0; i < 500'001; i++){
        dist[i] = INT_MAX;
    }
}

void make_roads(vector<vector<int>> _roads){
    for(int i = 0; i < _roads.size(); i++){
        roads[_roads[i][0]].push_back(_roads[i][1]);
        roads[_roads[i][1]].push_back(_roads[i][0]);
    }
}

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

void dijkstra(int root){
    dist[root] = 0;
    priority_queue<pair<int,int>,vector<pair<int,int> >, cmp> pq;
    // node, cost
    pair<int,int> cur;
    cur.first = root; cur.second = dist[root];
    pq.push(cur);
    while(!pq.empty()){
        cur = pq.top();
        pq.pop();
        // 최소 cost가 아닌 경우 pass
        if(dist[cur.first] < cur.second){
            continue;
        }
        // 이 노드의 인접 노드 중, 이 노드를 거쳐갈 경우의 최소 cost 업데이트
        for(int i = 0; i < roads[cur.first].size(); i++){
            int next_node = roads[cur.first][i];
            if(dist[next_node] > cur.second + 1){
                dist[next_node] = cur.second + 1;
                pq.push(make_pair(next_node, dist[next_node]));
            }
        }
    }
}

// 각 부대원의 최단시간 복귀 시간=?
// 총 지역 수 n, 길 정보 roads, 부대원 위치 sources, 강철부대 지역 destination
// sources의 원소 순서대로 최단시간 리턴. 복귀 불가능하면 -1.
vector<int> solution(int n, vector<vector<int>> _roads, vector<int> sources, int destination) {
    vector<int> answer;
    N = n;
    make_roads(_roads);
    // destination에서 각 sources까지의 최단 거리 찾기.
    // => 다익스트라 알고리즘
    init_dist();
    dijkstra(destination);
    for(int i = 0; i < sources.size(); i++){
        if(dist[sources[i]] == INT_MAX){
            answer.push_back(-1);
        }
        else{
            answer.push_back(dist[sources[i]]);
        }
    }
    return answer;
}

---------------------------------------------------후기----------------------------------------------------

여러 점에서 특정 하나의 점으로 가는 거리 = 뒤집어서 생각하면 한 점에서 다른 정점들까지의 거리.

즉, 다익스트라 알고리즘이 제일 먼저 떠올랐다.

 

다익스트라 알고리즘은 다음과 같이 진행된다.

출발노드 기준으로 다른 모든 노드까지의 거리 저장

->미방문 노드 중 최소 비용을 가지는 노드 선택

->이 노드를 거쳐 다른 노드로 가는 비용을 비교해 최소 비용으로 업데이트

모든 노드를 방문할 때까지 반복

 

계속 까먹는데, 자주 나오는 알고리즘이니까 꼭 기억해 둬야 한다..