[프로그래머스][C++] 부대복귀

부대복귀

문제 링크

부대복귀

분석

각 부대원의 위치에서 목표 지점까지 최단 시간(거리)를 구해야합니다.
만약 복귀가 불가능한 경우 해당 부대원의 최단시간은 -1입니다.

길은 모두 양방향이며, 이동 시간은 모두 1로 동일합니다.
즉, 가중치가 1로 동일한 무방향 그래프입니다.

• n은 현재 위치를 포함한 총 지역의 수입니다.
• roads는 두 지역을 왕복할 수 있는 길 정보를 담은 2차원 정수 배열입니다.
• sources는 복귀해야 하는 각 부대원의 위치들을 나타내는 정수 배열입니다.
• destination은 강철부대가 위치한 지역입니다.

풀이

#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>> graph(n + 1);
    
    // roads를 순회하여 양방향 그래프를 구성합니다.
    for (const auto& road : roads)
    {
        int a = road[0];
        int b = road[1];
        
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    // 각 지역에서 destination까지의 최단 거리를 저장할 배열입니다.
    vector<int> distance(n + 1, -1);
    
    // BFS 탐색에 사용할 큐입니다.
    queue<int> q;
    
    // 시작 지점은 부대가 위치한 지역을 의미하는 destination입니다.
    q.push(destination);
    distance[destination] = 0;
    
    // BFS 수행
    while(!q.empty())
    {
        // 현재 방문 중인 지역
        int cur = q.front();
        q.pop();
        
        // 현재 지역과 연결된 모든 이웃 지역을 확인합니다.
        for (int next : graph[cur])
        {
            // 아직 방문하지 않은 지역인 경우
            if (distance[next] == -1)
            {
                // 다음 지역까지의 거리를 저장하고, 다음 지역을 큐에 추가하여 이후 탐색을 진행합니다.
                distance[next] = distance[cur] + 1;
                q.push(next);
            }
        }
    }
    
    // 각 부대원이 위치한 지역에서 destination까지의 거리 값을 반환할 배열에 저장합니다.
    for (int source : sources)
    {
        answer.push_back(distance[source]);
    }
    
    return answer;
}

무방향 그래프를 인접 리스트로 표현합니다.

destination에서 BFS 탐색으로 각 정점까지의 최소 시간을 계산해줍니다.

sources배열을 순회하면서, 해당 위치의 최단 거리 값을 정답 배열에 추가해줍니다.
이때, 거리가 계산되지 않았던 노드인 경우 -1을 정답 배열에 추가합니다.

성능 요약

시간 복잡도는 $O(e + v + s)$입니다.

• 그래프를 구성하는 반복문 $O(e)$
  • e는 roads 배열의 크기를 의미하며, 간선의 개수입니다.
• BFS 수행 $O(e + v)$
  • v는 정점의 수를 의미합니다.
• sources을 순회하는 반복문 $O(s)$
  • s는 sources 배열의 크기를 의미합니다.
• $O(e) + O(e + v) + O(s)$

공간 복잡도는 $O(e + v + s)$입니다.

• 그래프를 저장하기 위한 인접 리스트 vector<vector<int>> graph $O(e + v)$
• 거리 정보를 저장하는 배열 vector<int> distance $O(n + 1)$
• BFS 용도의 큐 queue<int> q $O(v)$
• 결과 반환용 vector<int> answer $(s)$
• $O(e + v) + O(n) + O(v) + O(s)$

테스트 성능

테스트 1 〉 통과 (0.01ms, 4.14MB)
테스트 2 〉 통과 (0.01ms, 4.29MB)
테스트 3 〉 통과 (0.01ms, 4.23MB)
테스트 4 〉 통과 (0.01ms, 4.18MB)
테스트 5 〉 통과 (0.01ms, 4.14MB)
테스트 6 〉 통과 (4.76ms, 9.55MB)
테스트 7 〉 통과 (5.20ms, 10.4MB)
테스트 8 〉 통과 (6.52ms, 17MB)
테스트 9 〉 통과 (2.55ms, 7.66MB)
테스트 10 〉 통과 (4.56ms, 8.66MB)
테스트 11 〉 통과 (87.76ms, 106MB)
테스트 12 〉 통과 (96.03ms, 106MB)
테스트 13 〉 통과 (105.64ms, 106MB)
테스트 14 〉 통과 (89.58ms, 106MB)
테스트 15 〉 통과 (89.48ms, 106MB)
테스트 16 〉 통과 (21.50ms, 27.5MB)