[프로그래머스] 부대복귀 C++ (Lv.3)

 

 

 

 

 

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;
}

 

프로그래머스 - 결과 화면