문제 조건

input

• 노드의 개수 n
  • 3 ≤ n ≤ 100,000
• 간선 정보를 기록한 이차원 배열 roads
  • 2 ≤ roads ≤ 500,000
• 부대원의 위치 sources
  • 1 ≤ sources의 길이 ≤ 500
• 도착 지점
  • 1 ≤ destination ≤ n

output

• sources에서 destination까지의 최단 거리 배열

문제 해석

• BFS로 최단 거리 탐색
• 갈 수 없는 케이스도 존재 → -1리턴
• 현재 위치와 도착점이 같은 경우 → 0리턴
• 시작점을 기준으로 출발하는 것이 아니라, 도착지점을 기준으로 출발해서 거리 측정

코드

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

using namespace std;

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer;
    vector<vector<int>> g(n+1); // 간선 정보를 graph로 변환
    vector<int> distances(n+1, -1); // 거리 정보를 기록할 vector
                                    // 초기값은 -1로 설정
                                    // 1. 갈 수 없는 경로에 대한 고려
                                    // 2. 아직 방문하지 않은 노드 처리
    
    // 그래프 변환
    for (auto r : roads) {
        g[r[0]].push_back(r[1]);
        g[r[1]].push_back(r[0]);
    }
    
    queue<int> q;
    q.push(destination); // 도착지점부터 역으로 연산
                         // 도착 지점에서 sources[i]에 갈 수 없다면, -1로 남아있을 것임
                         // 갈 수 있다면 방문할 때마다 level+1 해주면서 경로 탐색
    distances[destination] = 0; // 자기 자신이 도착 지점에 이미 위치할 수 있음

    while (!q.empty()) {
        int s = q.front();
        q.pop();
            
        for (auto n : g[s]) {
            if (distances[n] == -1) { // 방문하지 않은 노드 처리
                distances[n] = distances[s] + 1;
                q.push(n);
            }
        }
    }
    
    // BFS로 탐색 완료 후, 거리를 정답 양식에 맞게 수정
    for (auto source : sources) {
        answer.push_back(distances[source]);
    }
    
    return answer;
}