[프로그래머스] 부대복귀 (C++)

문제 링크:https://school.programmers.co.kr/learn/courses/30/lessons/132266

프로그래머스

1. 주의할 점

- 한 지점부터 다른 지점까지의 최단 거리를 구하는 알고리즘은 대표적으로 다익스트라, 플로이드 와샬, 벨만포드가 존재

이때 N은 최대 10만이다

플로이드 와샬은 O(N^3) → TLE 발생 확률 매우 높아보인다

벨만포드는 간선에 음수가 있을 때 사용하는 다익스트라의 심화버전이지만 현재는 모든 간선에 1이라는 양수값만 있으므로 Pass

결국, 다익스트라 채택

- Source → Destination까지 갈 때, 이미 구한 최단 거리는 이용해도 되지 않을까?

 

2. 구현

- 다익스트라 알고리즘을 통해 각 Source에서 목적지 까지의 거리를 구한다.

- 단, 위에 2번째로 적은 주의할 점과 같이 이미 구한것을 또 구할 필요가 있을까? 발상의 전환을 해보자

- 결국 Source에서 목적지까지 모두 가야한다(못가는 것 제외). 그렇다면 반대로, 목적지에서 각 Source까지 가면 다익스트라 알고리즘 1번에 끝나겠는데?

- 각 Source → 목적지 N번 : N번의 다익스트라. 목적지 → 각 Source : 1번의 다익스트라

#define MAXI 987654321
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct info{
    int idx, val;		// Node, Node까지 걸리는 거리
};

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer;
    vector<vector<int>> node(n+1);   //간선 정보
    vector<int> dist(n+1);           //dest부터 각 source 까지의 거리
    //사전 준비
    for(int i=0;i<roads.size();i++){
        int a = roads[i][0];
        int b = roads[i][1];
        node[a].push_back(b);
        node[b].push_back(a);
    }
    
    for(int i=1;i<=n;i++)
        dist[i] = MAXI;
    
    // 다익스트라 시작
    queue<info> q;
    q.push({destination, 0});
    dist[destination] = 0;
    
    while(!q.empty()){
        info ii = q.front();
        q.pop();
        int cidx = ii.idx;
        int cv = ii.val;
        
        for(int i=0;i<node[cidx].size();i++){
            int next = node[cidx][i];
            if(dist[next] > cv + 1){
                dist[next] = cv + 1;
                q.push({next, cv+1});
            }
        }
    }
    // 다익스트라 끝
    
    for(int i=0;i<sources.size();i++){
        int val = dist[sources[i]] == MAXI ? -1 : dist[sources[i]];
        answer.push_back(val);
    }
    return answer;
}