[Algorithm] Programmers :: 부대복귀

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

프로그래머스

 

다익스트라 풀이 및 시간

struct Node
{
    int vertex;
    int distance;
};
 
struct cmp
{
    bool operator() (Node& a, Node& b)
    {
        return a.distance > b.distance;
    }
};
 
int dist[100001];
vector<vector<Node>> graph(100001);
 
vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) 
{
    vector<int> answer;
    memset(dist, 0x3f, sizeof(dist));
 
    for (int i = 0; i < roads.size(); ++i)
    {
        int a = roads[i][0];
        int b = roads[i][1];
 
        graph[a].push_back({ b,1 });
        graph[b].push_back({ a,1 });
    }
 
    dist[destination] = 0; // 출발
    priority_queue<Node, vector<Node>, cmp> pq;
    pq.push({ destination,0 });
 
    while (!pq.empty())
    {
        int curVertex = pq.top().vertex;
        int curDistance = pq.top().distance;
        pq.pop();
 
        if (dist[curVertex] < curDistance) continue;
 
        for (int i = 0; i < graph[curVertex].size(); ++i)
        {
            int nextVertex = graph[curVertex][i].vertex;
            int nextDistance = graph[curVertex][i].distance;
 
            if (curDistance + nextDistance < dist[nextVertex])
            {
                dist[nextVertex] = curDistance + nextDistance;
                pq.push({ nextVertex,curDistance + nextDistance });
            }
        }
    }
 
    for (int i = 0; i < sources.size(); ++i)
    {
        if (dist[sources[i]] == 0x3f3f3f3f) answer.push_back(-1);
        else answer.push_back(dist[sources[i]]);
    }
 
    return answer;
}

 

 

그냥 문제를 직관적으로 봤을때는 각 부대원의 위치에서 목표위치까지의 최단거리를 구해야하니 부대원명수 만큼 최단거리를 구하는 로직(다익이든,BFS든)을 수행해야할 것 같지만, 사실 목표위치가 정해져있기 때문에 목표위치를 시작으로 각 정점에 대해 최단거리를 구하는 로직을 한번만 수행하면 된다.

그것 말고는 특별할 게 없는 문제.