https://school.programmers.co.kr/learn/courses/30/lessons/132266
이번 문제는 bfs 문제였습니다.
📝 문제 풀이
1. 길 연결 정보를 info 벡터에 저장
2. sources 벡터를 순회하며 bfs 수행
➡️ sources[i]에서 강철 부대까지의 최단 거리 탐색
3. result를 갱신한 적이 없으면 answer.push_back(-1)
4. 최단 경로를 찾았다면 answer.push_back(result)
👩🏻💻 C++ 코드
#include <string>
#include <vector>
#include <queue>
#define MAX 100001
using namespace std;
int bfs(int source, int destination, vector<vector<int>> &info) {
queue<pair<int, int>> q;
bool visited[MAX] = {0};
int result = 2147000000;
q.push({source, 0});
visited[source] = true;
while (!q.empty()) {
int region = q.front().first;
int cnt = q.front().second;
q.pop();
if (region == destination) {
result = min(result, cnt);
}
for (int i=0; i<info[region].size(); i++) {
if (!visited[info[region][i]]) {
visited[info[region][i]] = true;
q.push({info[region][i], cnt + 1});
}
}
}
return result;
}
vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
vector<int> answer;
vector<vector<int>> info(n+1);
for (int i=0; i<roads.size(); i++) {
info[roads[i][0]].push_back(roads[i][1]);
info[roads[i][1]].push_back(roads[i][0]);
}
for (int i=0; i<sources.size(); i++) {
if (sources[i] == destination) {
answer.push_back(0);
continue;
}
int result = bfs(sources[i], destination, info);
if (result == 2147000000) {
answer.push_back(-1);
continue;
}
answer.push_back(result);
}
return answer;
}
반응형
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 구명보트 C++ (Lv.2) (0) | 2023.04.18 |
---|---|
[프로그래머스] 등대 C++ (Lv.3) (0) | 2023.04.18 |
[프로그래머스] 할인 행사 C++ (Lv.2) (0) | 2023.04.18 |
[프로그래머스] 귤 고르기 C++ (Lv.2) (0) | 2023.04.18 |
[프로그래머스] 연속된 부분 수열의 합 C++ (0) | 2023.04.14 |