프로그래머스 부대복귀 c++

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
    
vector<int> r[100001];
int des;
int minResult = 9999999;


void bfs(int x) {
    bool check[100001] = {false,};
    queue<pair<int,int>> q;
    q.push({x,0});
    check[x] = true;
    
    while(!q.empty()) {
        int nx = q.front().first;
        int cnt = q.front().second;
        q.pop();
        
        if(nx == des) { 
            minResult = min(minResult,cnt); 
            return;
        }
        
        for(int i=0; i<r[nx].size(); i++) {
            if(check[r[nx][i]]) continue;
            check[r[nx][i]] = true;
            q.push({r[nx][i],cnt+1});
        }
    }
}
    
vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer;
    des = destination;
    
    for(int i=0; i<roads.size(); i++) {
        int a,b;
        a = roads[i][0];
        b = roads[i][1];
        r[a].push_back(b);
        r[b].push_back(a);
    }
    
    for(int i=0; i<sources.size(); i++) {
        bfs(sources[i]);
        if(minResult == 9999999) {
            answer.push_back(-1);
        }
        else {
            answer.push_back(minResult);
            minResult = 9999999;
        }
    }
    
    return answer;
}

 

**

단방향 그래프로 주어진 입력을 양방향 그래프로 바꾼 뒤 bfs 만 잘 써주면 되는 문제

bool check 를 선언해 이미 방문한 지역을 재방문 하지 않도록 해준다.