[Algorithm] 프로그래머스 부대복귀 - C++, BFS

프로그래머스

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

vector<int> edge[100001];

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer(sources.size());
    
    vector<int> costFromDestination(n + 1, -1);
    
    // make edge
    for(int i = 0; i < roads.size(); i++){
        edge[roads[i][0]].push_back(roads[i][1]);
        edge[roads[i][1]].push_back(roads[i][0]);
    }
    
    // find by bfs
    queue<pair<int, int>> q; // pos, count
    q.push({destination, 0});
    costFromDestination[destination] = 0;
    
    while(!q.empty()){
        auto curPos = q.front().first;
        auto curCount = q.front().second;
        q.pop();
        
        for(int i = 0; i < edge[curPos].size(); i++){
            int nextPos = edge[curPos][i];
            
            if(costFromDestination[nextPos] == -1 || costFromDestination[nextPos] > curCount + 1){
                q.push({nextPos, curCount + 1});
                costFromDestination[nextPos] = curCount + 1;
            }
        }
    }
    
    for(int i = 0; i < sources.size(); i++){
        answer[i] = costFromDestination[sources[i]];
    }
    
    return answer;
}

---

처음에는 플로이드 와샬인가 싶어서 배열을 선언하려는 찰나 [100001][100001] 배열을 보고 아찔해져서 다른 풀이법을 생각해 봤습니다. 어차피 도착 지점은 하나이니 도착 지점에서 BFS 같은 방식을 통해 모든 지점으로의 거리를 구하면 풀리는 문제였습니다. 역발상을 해야 한다는 문제지만 코드는 레벨 3인가? 싶을 정도로 쉽게 나왔네요.