부대복귀

https://school.programmers.co.kr/learn/courses/30/lessons/132266

구현 아이디어 10분 구현 20분

풀이(시간 초과)

출발 정점이 여러 개라 플로이드-워샬 알고리즘을 썼는데 시간 초과가 떴다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer;
    
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 100000));
    for(int i = 1; i <= n; ++i) dp[i][i] = 0;
    
    for(int i = 0; i < roads.size(); ++i)
    {
        int r = roads[i][0];
        int c = roads[i][1];
        dp[r][c] = 1;
        dp[c][r] = 1;
    }
    
    // j에서 k까지 갈 때 i번 정점을 거쳐서 가는 경우.
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= n; ++j)
        {
            for(int k = 1; k <= n; ++k)
            {
                dp[j][k] = dp[j][k] < dp[j][i] + dp[i][k] ?
                    dp[j][k] : dp[j][i] + dp[i][k];
            }
        }
    }
    
    for(int i = 0; i < sources.size(); ++i)
    {
        if(dp[sources[i]][destination] != 100000) answer.push_back(dp[sources[i]][destination]);
        else answer.push_back(-1);
    }
    
    return answer;
}

---

풀이(다익스트라)

출발 정점은 여러 개지만 도착 정점은 하나다. 즉, 도착 정점에서 각 출발 정점까지 가는 최단 거리를 구하면 되는 문제.

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

using namespace std;

// destination은 하나. destination부터 sources까지 가는 거리 구하면 됨.
bool visited[100001];
vector<int> maps[100001];

struct Data
{
    int index, dist;
    Data(int index, int dist)
    {
        this->index = index;
        this->dist = dist;
    }
    bool operator<(const Data& b) const
    {
        return dist > b.dist;
    }
};

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer;
    vector<int> dist(n + 1, 2147000000);
    dist[destination] = 0;
    
    for(int i = 0; i < roads.size(); ++i)
    {
        maps[roads[i][0]].push_back(roads[i][1]);
        maps[roads[i][1]].push_back(roads[i][0]);
    }
    
    priority_queue<Data> pQ;
    pQ.push(Data(destination, 0));
    
    while(!pQ.empty())
    {
        Data cur = pQ.top();
        pQ.pop();
        
        visited[cur.index] = true;
        
        for(int i = 0; i < maps[cur.index].size(); ++i)
        {
            int check_index = maps[cur.index][i];
            if(!visited[check_index] && dist[cur.index] + 1 < dist[check_index])
            {
                dist[check_index] = dist[cur.index] + 1;
                pQ.push(Data(check_index, dist[check_index]));
            }
        }
    }
    
    for(int i = 0; i < sources.size(); ++i)
    {
        if(dist[sources[i]] == 2147000000) answer.push_back(-1);
        else answer.push_back(dist[sources[i]]);
    }
    
    return answer;
}