[프로그래머스] 연습문제>부대복귀

문제 설명

강철부대의 각 부대원이 여러 지역에 뿔뿔이 흩어져 특수 임무를 수행 중입니다. 지도에서 강철부대가 위치한 지역을 포함한 각 지역은 유일한 번호로 구분되며, 두 지역 간의 길을 통과하는 데 걸리는 시간은 모두 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

 

프로그래머스 level3 BFS문제입니다.

road는 인접리스트로 새로 정의해주고, 출발지점들로부터 목적지까지 걸리는 시간은 1로 일정하기때문에 거리만 계산해주면 됩니다.

#include <string>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
vector<int>lst[500001]; //인접리스트

int bfs(int from,int to){
    int visited[1000001];
    memset(visited,-1,sizeof(visited));
 
    queue<int>q;
    visited[from]=0;
    q.push(from);
    while(!q.empty()){
        auto top=q.front();
        q.pop();
        if(top==to){
            return visited[top];
        }
        for(int i=0;i<lst[top].size();i++){

            if(visited[lst[top][i]]==-1){
                q.push(lst[top][i]);
                visited[lst[top][i]]=visited[top]+1;
            }
        }
    }
    return -1;
}
vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer;
    for(int i=0;i<roads.size();i++){
        int x=roads[i][0];
        int y=roads[i][1];
    
        lst[x].push_back(y);  //양방향으로 통과 가능
        lst[y].push_back(x);
    }
    
    for(int i=0;i<sources.size();i++){
        answer.push_back(bfs(sources[i],destination));  
    }
    return answer;
}