프로그래머스 - 부대복귀(Lv.3)

문제풀이1 (시간초과)

• DFS를 떠올렸으나, 어김없이 시간초과로 통과하지 못했다.
• 모든 부대원들에 대해서 목적지까지 최단거리를 탐색하다보니 시간복잡도가 O(n^2)이 된다.

구현(Time Exceed)

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> map[100001];

void come_back(int cur_node, int destination, int cnt, int& val, vector<bool>& visited){
    // 기저사례: 강철부대 위치로 돌아온 경우
    if(cur_node==destination) {
        if(cnt<val) val = cnt;
        return;
    }
    
    for(int i=0; i<map[cur_node].size(); i++){
        int next_node = map[cur_node][i];
        if(visited[next_node]==true) continue;
        visited[next_node] = true;
        come_back(next_node, destination, cnt+1, val, visited);
        visited[next_node] = false;
    }
    return;
}

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer;
    vector<bool> visited(n+1, false);
    
    // generate map
    for(int i=0; i<roads.size(); i++){
        int from = roads[i][0];
        int to = roads[i][1];
        map[from].push_back(to);
        map[to].push_back(from);
    }
    
    int val = 100000;
    for(int i=0; i<sources.size(); i++){
        val = 100000;
        visited[sources[i]] = true;
        come_back(sources[i], destination, 0, val, visited);
        visited[sources[i]] = false;
        if(val==100000) 
            answer.push_back(-1);
        else
            answer.push_back(val);
    }
    
    return answer;
}

개선한 점

• 목적지를 기준으로 모든 부대에 대해서 최단거리를 구한다.
• 목적지에서 도달할 수 없는 지역은 -1로 표시한다.
• bfs로 풀것

구현(All Pass)

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

using namespace std;

vector<int> map[100001];

void update_distance(vector<int>& min_distance, int cnode){
    int n = min_distance.size();
    vector<bool> visited(n+1, false);
    
    min_distance[cnode] = 0;
    visited[cnode]=true;
    
    queue<int> q;
    q.push(cnode);
    while(!q.empty()){
        cnode = q.front();
        q.pop();
        
        for(int i=0; i<map[cnode].size(); i++){
            int nnode = map[cnode][i];
            if(visited[nnode]==true) continue;
            visited[nnode] = true;
            q.push(nnode);
            min_distance[nnode]=min_distance[cnode]+1;
        }
    }
}

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer;
    vector<int> min_distance(n+1, -1);
    
    // Generate map
    for(int i=0; i<roads.size(); i++){
        int from = roads[i][0];
        int to = roads[i][1];
        map[from].push_back(to);
        map[to].push_back(from);
    }
    
    update_distance(min_distance, destination);
    
    for(int i=0; i<sources.size(); i++)
        answer.push_back(min_distance[sources[i]]);
    
    return answer;
}