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

프로그래머스

 

📄 문제

강철부대의 각 부대원이 여러 지역에 뿔뿔이 흩어져 특수 임무를 수행 중입니다. 지도에서 강철부대가 위치한 지역을 포함한 각 지역은 유일한 번호로 구분되며, 두 지역 간의 길을 통과하는 데 걸리는 시간은 모두 1로 동일합니다. 임무를 수행한 각 부대원은 지도 정보를 이용하여 최단시간에 부대로 복귀하고자 합니다. 다만 적군의 방해로 인해, 임무의 시작 때와 다르게 되돌아오는 경로가 없어져 복귀가 불가능한 부대원도 있을 수 있습니다.

강철부대가 위치한 지역을 포함한 총지역의 수 n, 두 지역을 왕복할 수 있는 길 정보를 담은 2차원 정수 배열 roads, 각 부대원이 위치한 서로 다른 지역들을 나타내는 정수 배열 sources, 강철부대의 지역 destination이 주어졌을 때, 주어진 sources의 원소 순서대로 강철부대로 복귀할 수 있는 최단시간을 담은 배열을 return하는 solution 함수를 완성해주세요. 복귀가 불가능한 경우 해당 부대원의 최단시간은 -1입니다.

 

📝 풀이

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;
vector<vector<int>> v;
vector<int> dist;

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    v = vector<vector<int>>(n + 1, vector<int>());
    dist = vector<int>(n + 1, -1);
    
    for(vector<int> road : roads)
    {
        v[road[0]].push_back(road[1]);
        v[road[1]].push_back(road[0]);
    }
    
    queue<int> q;
    q.push(destination);
    dist[destination] = 0;
    
    while(!q.empty())
    {
        int here = q.front();
        q.pop();
        
        for(int i = 0; i < v[here].size(); ++i)
        {
            int to = v[here][i];
            if(dist[to] != -1)
                continue;
            
            q.push(to);
            dist[to] = dist[here] + 1;
        }
    }
    
    vector<int> answer;
    for(int n : sources)
        answer.push_back(dist[n]);
    
    return answer;
}

• BFS를 이용하여 문제를 해결하였습니다.
• dist를 -1로 모두 초기화합니다. 단 한번도 해당 노드를 방문하지 못하는경우, -1로 리턴할 수 있게 합니다.
• 시작점에서 가까운 노드들을 먼저 방문하고, 그 다음에는 그 노드들과 인접한 노드들을 방문하게 됩니다. 이런식으로 하나씩 계속해서 가까운 순서대로 이동하면, 최종적으로 목표 지점까지의 가장 짧은 경로를 찾을 수 있습니다.
• while을 시작하기 전 push를 시작점인 destination을 삽입하여 모든 노드에 대하여 검색하도록 합니다.
• q가 empty가 되어 while문을 빠져나온경우, sources를 순회하여 dist의 값을 answer에 차례대로 삽입합니다.