[프로그래머스] Level 3. 부대 복귀

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

프로그래머스

 

해결 방법

이 문제는 Level 2. 배달  문제와 동일하게 다익스트라 알고리즘으로 푸는 문제이다. 여기에서 몇가지 주의사항이 늘어나서 Level 3이다.

1. 문제에서 제공한대로 각 지점에서 desination까지의 거리를 각각 찾지말고, destination을 출발지점으로 정하고 다익스트라를 하면 각 지점까지의 최소거리가 나온다. 
2. 지점의 수는 10만개까지이다. 즉 맵이 너무 크기때문에, 맵 정보 저장시 10만x10만의 배열로 만드는 것은 너무 비효율적이다. 그러니 2차 배열로 하되, 연결정보가 있는 지점정보만 넣는다.
3. 간선들의 가중치에 차이가 없이 모두 1만큼의 거리를 가지고있다. 따라서, 매번 검사 시에 누구를 검사할지 dist를 돌면서 검사하지 않아도 된다. 내 옆노드를 검사하면서 queue에 넣어준 뒤, 순서대로 검사하는 것으로 충분하다.

 

#include <string>
#include <vector>
#include <climits>
#include <queue>
using namespace std;

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer;
    vector<bool> visited(n,false);
    vector<int> dist(n,INT_MAX);
    
    //맵 초기화. 양방향 이동가능함. 가중치는 1임.
    vector<vector<int>> maps(n);
    for(int i=0; i<roads.size();i++){
        int s= roads[i][0]-1; int e = roads[i][1]-1;
        maps[s].push_back(e);
        maps[e].push_back(s);
    }
    
    //도착지에서 각 지점까지의 최소거리를 구한다
    dist[destination-1] = 0;
    queue<int> q;
    q.push(destination-1);
    
    while(!q.empty()){
        int idx= q.front();
        q.pop();
        
        //인접한 노드들에게 
        for(int node : maps[idx]){
            dist[node] = min(dist[node], dist[idx] + 1);
            if(!visited[node]) q.push(node);
        }
        visited[idx] = true;
    }
    
    for(int i=0; i<sources.size() ; i++){
        int node =sources[i]-1;
        
        answer.push_back(dist[node] == INT_MAX ? -1 : dist[node]);
    }
    
    return answer;
}