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

문제

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

프로그래머스

풀이

아주 일반적인 BFS문제.

destination(start)부터 BFS를 돌면서, 각각 노드 첫번째 방문시에 얼마나 걸렸는지(cnt)를 배열(dist)에 넣어준다.

방문 전에 배열은 -1로 초기화하고, 처음 방문시에 걸린 횟수(cnt)를 넣어준다.

BFS 특성상 가장 첫 방문이 최단 거리이므로 dist값이 -1이 아니라면 이미 방문한 노드이니 갱신해주지 않는다.

BFS를 끝내면 sources에 들어있는 노드까지 얼마나 걸리는지를 answer에 넣어준다.

소스 코드

#include <string>
#include <vector>
#include <queue>
using namespace std;
 
vector<int> map[100001];
int dist[100001];
 
void Bfs(int start)
{
    dist[start] = 0;
    queue<pair<int, int>> q;
    q.push(make_pair(start, 0));
    
    while(!q.empty())
    {
        int cur = q.front().first;
        int cnt = q.front().second;
        q.pop();
        
        for (int i = 0; i < map[cur].size(); i++)
        {
            int next = map[cur][i];
            if(dist[next] == -1)
            {
                dist[next] = cnt + 1;
                q.push(make_pair(next, cnt + 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++)
    {
        int a = roads[i][0];
        int b = roads[i][1];
        map[a].push_back(b);
        map[b].push_back(a);
    }
    
    for (int i = 0; i < 100001; i++)
    {
        dist[i] = -1;
    }
    
    Bfs(destination);
    
    for (int i = 0; i < sources.size(); i++)
    {
        answer.push_back(dist[sources[i]]);
    }
    
    return answer;
}