[프로그래머스] 부대 복귀 [C++]

 

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

프로그래머스

 

 

문제 분석

주어진 문제는 각 부대원이 복귀할 수 있는 최단 경로를 찾아야 하는 전형적인 최단 경로 문제입니다. 부대가 위치한 지역에서 각 부대원들이 출발한 지역으로부터의 최단 경로를 구하는 것이 목적입니다.

문제는 각 부대원으로부터 목적지까지의 최단 거리를 구해야 하는것 처럼 나와있지만, 역으로 생각하면, 목적지에서 부대원들까지의 최단 거리를 한번만 구하면 풀 수 있는 문제입니다.

1. 지역간의 길은 모두 양방향이다
2. 모든 길의 비용은 1 로 동일하다

코드

#include <bits/stdc++.h>
using namespace std;

/*
 * 두 지역 간의 길을 통과 하는데 걸리는 시간은 모두 1
 * 각 부대원 은 최단 시간 부대로 복귀 하고자 한다
 * 
 * 총 지역의 수                      = n
 * 왕복할 수 있는 길 2차원 배열        = roads
 * 서로 다른 지역들을 나타내는 정수 배열 = sources
 * 부대의 지역                       = destination
 *
 * sources 의 원소 순서대로 강철부대로 복귀할 수 있는 최단시간 배열 을 구해야 한다
 * 복귀가 불가능할 경우 -1
 *
 */

vector<vector<int>> graph;  // 인접 리스트로 그래프를 표현
vector<int> dist;           // 각 노드까지의 최단 거리를 저장할 배열

// 다익스트라 알고리즘: 주어진 node(destination)에서 다른 모든 노드까지의 최단 경로 계산
void dijkstra(int node) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, node});  // 시작 노드와 비용을 우선순위 큐에 삽입 (비용, 노드)
    dist[node] = 0;      // 시작 지점의 거리는 0

    while (!pq.empty()) {
        int current_cost = pq.top().first;  // 현재 노드까지의 비용
        int current_node = pq.top().second; // 현재 노드
        pq.pop();

        // 이미 처리된 노드면 넘어감
        if (dist[current_node] < current_cost) continue;

        // 인접한 노드들을 확인
        for (int next_node : graph[current_node]) {
            int next_cost = current_cost + 1;  // 모든 간선의 비용이 1이므로

            // 더 짧은 경로를 발견하면 업데이트하고 큐에 삽입
            if (dist[next_node] > next_cost) {
                dist[next_node] = next_cost;
                pq.push({next_cost, next_node});
            }
        }
    }
}

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    // 그래프 초기화
    graph.resize(n + 1);
    dist.resize(n + 1, INT_MAX);  // 초기 거리는 무한대로 설정

    // roads를 이용해 양방향 그래프 구성
    for (const auto& road : roads) {
        int a = road[0];
        int b = road[1];
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    // destination에서 시작하는 다익스트라 실행
    dijkstra(destination);

    // sources의 각 지역에서 부대(destination)로 갈 수 있는 최단 시간을 answer에 기록
    vector<int> answer;
    for (int source : sources) {
        if (dist[source] == INT_MAX) {
            answer.push_back(-1);  // 복귀 불가능한 경우
        } else {
            answer.push_back(dist[source]);  // 최단 시간
        }
    }

    return answer;
}