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

 

생각을 잘못했다. 처음에 예외케이스를 생각하지 못했다.

예외 케이스를 생각하지 못한 풀이로, 시간을 많이 소요했다.

 

만약 4에서 1 3 5 갈 수 있는데

 

1에 최단거리 값이 map에 저장되어 있다 해서 3 5를 무시하고 리턴하면 안된다.

3에서 가는 값이 더 최단일 수 있다.

 

따라서 destination 기준으로 bfs를 한번 돌아서 map값을 만들어놓고 사용하면 된다.

#include <cstring>
#include <vector>
#include <map>
#include <iostream>
#include <queue>

using namespace std;


vector<int> link[100001]; // == vector<vector<int>> link(100001);
bool VISIT[100001];
map<int, int> dp;


void bfs(int start) {
    
    queue<pair<int, int>> que;
    
    que.push({start, 0});
    VISIT[start] = true;
    
    while(!que.empty()) {
        
        int key = que.front().first;
        int depth = que.front().second;
        
        dp[key] = depth;
        
        que.pop();
        
        for(int i = 0; i < link[key].size(); i++) {
            
            int value = link[key][i];
            
            if(!VISIT[value]) {
                
                que.push({value, depth + 1});
                VISIT[value] = true;
                
            }
            
        }
        
        
    }    
}

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer;
    
    for(auto road : roads) {
        link[road[0]].push_back(road[1]);
        link[road[1]].push_back(road[0]);
    }
    
    
    // 목적지에서 각 source 로 가는 최단거리를 한번에 다 구해냄.
    bfs(destination);
    
    
    for(auto source : sources) {
        
        int value = dp[source];
        
        if(VISIT[source])
            answer.push_back(value);
        else
            answer.push_back(-1);
    }
    
    
    return answer;
}