C++:: 프로그래머스 < 부대복귀 >

처음에 dfs로 접근을 했다가 시간초과가 난 문제이다. bfs로 접근하여 풀면 쉬운문제이지만 해당 방법이 생각나지않아서 애를 먹은 문제이다.
문제 풀이의 핵심은 목표지점에서 역으로 카운트를 한다는 점이다.

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

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer, cost(n + 1, -1), map[100001];
    
    for(auto road : roads){//연결된 노드들 정보 저장
        map[road[0]].push_back(road[1]);
        map[road[1]].push_back(road[0]);
    }

    queue<pair<int, int>> q;
    q.push({destination, 0});// 시작점 넣어준다.
    cost[destination] = 0;// 바로 목표지점에서 시작하는 경우도 존재하므로 0으로 해주어야한다.
    
    while (!q.empty()) {
        int curPos = q.front().first;
        int curCost = q.front().second;
        q.pop();
        for (auto nextPos : map[curPos]) {// 현재 위치에서 갈수있는 nextpos들
            if (cost[nextPos] == -1 || cost[nextPos] > curCost + 1) {
            	// 이전에 도착한적 없거나 그값이 현재까지의 cost + 1 보다 크다면 갱신
                q.push({nextPos, curCost + 1});
                cost[nextPos] = curCost + 1;
            }
        }
    }
    for (auto src : sources) answer.push_back(cost[src]);
    return answer;
}