코딩 테스트 - 부대복귀

부대복귀

문제 링크 : 부대복귀

문제 설명

강철부대의 각 부대원이 여러 지역에 뿔뿔이 흩어져 특수 임무를 수행 중입니다. 지도에서 강철부대가 위치한 지역을 포함한 각 지역은 유일한 번호로 구분되며, 두 지역 간의 길을 통과하는 데 걸리는 시간은 모두 1로 동일합니다. 임무를 수행한 각 부대원은 지도 정보를 이용하여 최단시간에 부대로 복귀하고자 합니다. 다만 적군의 방해로 인해, 임무의 시작 때와 다르게 되돌아오는 경로가 없어져 복귀가 불가능한 부대원도 있을 수 있습니다.

강철부대가 위치한 지역을 포함한 총지역의 수 n, 두 지역을 왕복할 수 있는 길 정보를 담은 2차원 정수 배열 roads, 각 부대원이 위치한 서로 다른 지역들을 나타내는 정수 배열 sources, 강철부대의 지역 destination이 주어졌을 때, 주어진 sources의 원소 순서대로 강철부대로 복귀할 수 있는 최단시간을 담은 배열을 return하는 solution 함수를 완성해주세요. 복귀가 불가능한 경우 해당 부대원의 최단시간은 -1입니다.

제한 사항

• 3 ≤ n ≤ 100,000
  • 각 지역은 정수 1부터 n까지의 번호로 구분됩니다.
• 2 ≤ roads의 길이 ≤ 500,000
  • roads의 원소의 길이 = 2
  • roads의 원소는 [a, b] 형태로 두 지역 a, b가 서로 왕복할 수 있음을 의미합니다.(1 ≤ a, b ≤ n, a ≠ b)
  • 동일한 정보가 중복해서 주어지지 않습니다.
    • 동일한 [a, b]가 중복해서 주어지지 않습니다.
    • [a, b]가 있다면 [b, a]는 주어지지 않습니다.
• 1 ≤ sources의 길이 ≤ 500
  • 1 ≤ sources[i] ≤ n
• 1 ≤ destination ≤ n

입출력 예

n	roads	sources	destination	result
3	[[1, 2], [2, 3]]	[2, 3]	1	[1, 2]
5	[[1, 2], [1, 4], [2, 4], [2, 5], [4, 5]]	[1, 3, 5]	5	[2, -1, 0]

풀이 방법

• 최단거리를 구하는 문제인데, 출발점에서 도착점으로 도달하는 시간을 구하는 문제인데 출발점이 여러 개이기 때문에 반대로 도착점을 출발점으로 생각하여 모든 도착점을 구하여서 sources에 있는 값들만 반환하고자 했다.
• 노드 간의 가중치가 없이 경로 모두가 1이기 때문에 bfs를 통해서 문제를 풀고자 했다. 또한 그래프를 표현할 때는 시간복잡도를 위해서 인접 리스트를 통해 구현했다.
  -> 해당 문제 풀이는 인접 리스트를 통한 bfs 구현이기 때문에 O(V+E)의 시간복잡도가 걸릴 것으로 추정되고, V는 최대 100,000이고, E는 최대 500,000이기 때문에 알맞은 알고리즘으로 보인다.

구현

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

using namespace std;

struct node {
    int to;
    int cost;
};

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer;
    
    // 인접 리스트
    vector<vector<int>> graph(n + 1);
    for(vector<int> v : roads){
        graph[v[0]].push_back(v[1]);
        graph[v[1]].push_back(v[0]);
    }
    
    // bfs
    vector<int> distance(n + 1, -1);
    vector<bool> visited(n + 1, false);
    queue<node> Q;
    
    Q.push({destination, 0});
    distance[destination] = 0;
    visited[destination] = true;
    
    while(!Q.empty()){
        node k = Q.front(); Q.pop();
        
        for(int i : graph[k.to]){
            if(!visited[i]){
                Q.push({i, k.cost + 1});
                visited[i] = true;
                distance[i] = k.cost + 1;
            }
        }
    }
       
    // 출발지별로 정답 넣기
    for(int i : sources){
        answer.push_back(distance[i]);
    }
    
    return answer;
}