[Programmers] Lv3. 부대복귀 | C++

🔗문제 보러가기

프로그래머스

 

🧑‍💻풀이 과정

 

다익스트라 알고리즘을 활용하여 풀었습니다. 목적지(Destination)를 시작점으로 하여 각 지역에 대한 최단 거리 배열을 구하고, 출발지(source)들에 해당하는 값들을 answer 배열에 담아주었습니다.

 

만약 어떤 출발지의 최단 거리 값이 초깃값과 같다면, 그 지역은 못 간다는 의미이므로 -1을 담아주면 되구요. 또한, 모든 지역 간의 이동 비용이 1이므로, 우선순위 큐 대신 일반 큐를 활용하여 시간을 줄였습니다.

 

✏️소스 코드 및 결과

#include <vector>
#include <queue>
#define INF 1000000000

using namespace std;
using Data = pair<int, int>;    // <비용, 지역>

void Dijkstra(const vector<vector<int>>& routes, vector<int>& distances, int n, int source) {
    queue<Data> regions;
    distances[source] = 0;
    regions.emplace(0, source);
    
    while (!regions.empty()) {
        int cost = regions.front().first;
        int region = regions.front().second;
        regions.pop();
        
        if (cost < distances[region])
            continue;
        
        for (const int& nextRegion : routes[region]) {
            int nextCost = cost + 1;
            if (nextCost < distances[nextRegion]) {
                distances[nextRegion] = nextCost;
                regions.emplace(nextCost, nextRegion);
            }
        }
    }
}

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<vector<int>> routes(n + 1, vector<int>());
    for (const vector<int>& road : roads) {
        int from = road[0], to = road[1];
        routes[from].emplace_back(to);
        routes[to].emplace_back(from);
    }

    vector<int> answer;
    vector<int> distances(n + 1, INF);

    Dijkstra(routes, distances, n, destination);
    for (const auto& source : sources) {
        int distance = distances[source] == INF ? -1 : distances[source];
        answer.emplace_back(distance);        
    }
    
    return answer;
}