부대복귀

재밌는 문제를 풀었다. 그래프류의 문제였는데 일반적으로 보면은 쉽지만 약간의 튜닝이 있어야지 모든 테스트 케이스를 통과하는 문제다.

이렇게 roads 가 주어지면 soruces 를 따라가서 destination 에 닿는 최소 거리를 담고 반환하면 되는 문제다.

정말로 단순하게 생각하면은 각 sources 마다 bfs를 해줘서 destination 에 닿는 최소 거리를 담아서 result에 넣으면 되지만 제한 사항에 보면은 n의 숫자가 10^5 라서 visited 배열을 매번 초기화 해야하는 상황에서 같은 노드를 계속 탐색하는 거라 무조건 TLE 가 나온다.

더 최적화 하는 방법도 있겟지만 나의 경우, destination에 닿지 못하는 노드가 있을 경우, 어떤 방식으로 탐색하든 그 위치에서는 destination 에 못 닿는거라서 -1을 바로 반환 했다. 이렇게 튜닝을 한번 해줘야지 TLE 가 안걸린다.

#include <string>
#include <vector>
#include <bits/stdc++.h> 
using namespace std;

map<int,bool> hashMap; 
bool visited[100001]; 

int bfs(vector<vector<int>>& adj, int start, int destination){
    queue<pair<int,int>> q;
    q.push({start,0}); 
    if(start == destination) return 0; 
    visited[start] = true; 
    while(!q.empty()){
        int size = q.size();
        for(int i = 0; i < size; i++){
            pair<int,int> p = q.front();
            q.pop(); 
            int currNode = p.first, currDist = p.second; 
            if(currNode == destination) return currDist; 
            for(int next : adj[currNode]){
                if(hashMap.count(next)) return -1; 
                if(!visited[next]){
                    visited[next] = true; 
                    q.push({next, currDist + 1}); 
                }
            }
        }
    }
    return -1; 
}

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer;
    vector<vector<int>> adj(n + 1); 

    for(vector<int>& v : roads){
        adj[v[0]].push_back(v[1]);
        adj[v[1]].push_back(v[0]); 
    }
    
    for(int& start : sources){
        memset(visited,false,sizeof(visited)); 
        int dist = bfs(adj,start,destination);
        if(dist == -1) hashMap[start] = true; 
        answer.push_back(dist); 
    }
    
    return answer;
}