문제
강철부대의 각 부대원이 여러 지역에 뿔뿔이 흩어져 특수 임무를 수행 중입니다. 지도에서 강철부대가 위치한 지역을 포함한 각 지역은 유일한 번호로 구분되며, 두 지역 간의 길을 통과하는 데 걸리는 시간은 모두 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
BFS 탐색으로 최단 시간을 구하고자 했고, 나는 편의를 위해 주어진 roads로 간선 edge를 생성해 주었다.
#include <string>
#include <vector>
#include <queue>
using namespace std;
int n, destination;
vector<int> edge[100001];
int bfs(int start){
int cur, next;
//목적지에 도달할 수 없는 경우 -1 반환을 위해 초기값 -1로 설정
vector<int> visited(n+1, -1);
queue<int> q;
visited[start] = 0;
q.push(start);
while(!q.empty() && visited[destination] == -1){
cur = q.front(); q.pop();
for(int i = 0; i < edge[cur].size(); i++){
next = edge[cur][i];
if(visited[next] > -1) continue;
q.push(next);
visited[next] = visited[cur] + 1;
}
}
//목적지에 도달하지 못할 경우 초기값 -1반환
//목적지에 도달한 경우 이동 횟수(=최단시간) 반환
return visited[destination];
}
vector<int> solution(int _n, vector<vector<int>> roads, vector<int> sources, int _destination) {
vector<int> answer;
n = _n; destination = _destination;
int u, v;
//roads로 edge생성
for(int i = 0; i < roads.size(); i++){
u = roads[i][0], v = roads[i][1];
edge[u].push_back(v);
edge[v].push_back(u);
}
//각 부대원 위치에서 bfs를 수행하여 최단시간 구하기
for(int i = 0; i < sources.size(); i++)
answer.push_back(bfs(sources[i]));
return answer;
}
'Alrogithm > 프로그래머스(PROGRAMMERS)' 카테고리의 다른 글
[프로그래머스] 삼총사 (0) | 2022.11.23 |
---|---|
[프로그래머스] 롤케이크 자르기 (0) | 2022.11.23 |
[프로그래머스] 콜라 문제 (0) | 2022.11.23 |
[프로그래머스] 옹알이(2) (0) | 2022.11.23 |
[프로그래머스] 등대 (0) | 2022.11.22 |