[프로그래머스 Level 3] 부대복귀(C++)

https://school.programmers.co.kr/learn/courses/30/lessons/132266?language=cpp

프로그래머스

 

최단 경로를 찾는 문제이다. 목적지에서 출발하여 각각 지역까지의 거리를 계산하는 방식으로 했다.

 

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

vector<int> path[100001];
int cost[100001];

void bfs(int n){
    queue<pair<int, int>> q;
    q.emplace(n,0);
    while(!q.empty()){
        int node = q.front().first;
        int nowCost = q.front().second;
        q.pop();
        if(cost[node]!=-1){
            continue;
        }
        cost[node]=nowCost;
        for(int i = 0 ; i < path[node].size(); i++){
            q.emplace(path[node][i], nowCost+1);
        }
    }
}

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer;
    for(int i = 0; i<roads.size(); i++){
        path[roads[i][0]].push_back(roads[i][1]);
        path[roads[i][1]].push_back(roads[i][0]);
    }
    for(int i = 1; i<=n; i++){
        cost[i]=-1;
    }
    bfs(destination);
    for(int i = 0; i<sources.size(); i++){
        answer.push_back(cost[sources[i]]);
    }
    return answer;
}