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

프로그래머스

 

• 간단한 bfs/dfs 문제
• roads를 각 노드에 대한 인접 리스트로 만들어서 bfs를 수행하면 됨

 

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

// 그래프 문제
// 각 노드별 인접 리스트를 만들어서 bfs 돌리면 될듯

using namespace std;

int bfs(int startNode, int destination, vector<vector<int>> &list) {
    queue<pair<int, int>> q;
    bool isVisited[100001] = {false};
    int dist = INT32_MAX;
    
    q.push({startNode, 0});
    isVisited[startNode] = true;
    
    while(!q.empty()) {
        int curNode = q.front().first;
        int movedDist = q.front().second;
        q.pop();
        
        if(curNode == destination) {
            dist = min(dist, movedDist);
        } 
        
        for(int i = 0; i < list[curNode].size(); i++) {
            if(!isVisited[list[curNode][i]]) {
                isVisited[list[curNode][i]] = true;
                q.push({list[curNode][i], movedDist + 1});
            }
        }
    }
    
    return dist;
}

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer;
    vector<vector<int>> list(n + 1);
    
    // 리스트 생성
    for(int i = 0; i < roads.size(); i++) {
        list[roads[i][0]].push_back(roads[i][1]);
        list[roads[i][1]].push_back(roads[i][0]);
    }
    
    // 각 부대원 별로 bfs 수행
    for(int i = 0; i < sources.size(); i++) {
        // 이미 목적지에 위치해 있으면
        if(sources[i] == destination) {
            answer.push_back(0);
            continue;
        }
        
        int result = bfs(sources[i], destination, list);
        
        if(result == INT32_MAX) answer.push_back(-1);
        else answer.push_back(result);
    }
    
    return answer;
}