부대복귀

문제 설명

강철부대의 각 부대원이 여러 지역에 뿔뿔이 흩어져 특수 임무를 수행 중입니다. 지도에서 강철부대가 위치한 지역을 포함한 각 지역은 유일한 번호로 구분되며, 두 지역 간의 길을 통과하는 데 걸리는 시간은 모두 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

입출력 예

n	roads	sources	destination	result
3	[[1, 2], [2, 3]]	[2, 3]	1	[1, 2]
5	[[1, 2], [1, 4], [2, 4], [2, 5], [4, 5]]	[1, 3, 5]	5	[2, -1, 0]

---

문제 해설

 

전체 노드를 탐색하되, 중복되는 탐색 결과는 피하라 는 문제이다.

 

모든 그래프를 탐색하는데 들어가는 비용이 최소한이 되려면, 중복되는 노드 탐색결과는 없어야 한다는 점을 생각하자.

 

만약, 중복되는 노드가 더 짧은 거리인지 아닌지 현재가 더 긴지 아닌지 판별하기 어렵다고 한다면, 출발지 기준으로 전체를 탐색하기 보다는, 목표 기준으로 전채 탐색을 한 뒤에, 방문한 노드 와 거리를 정리한 해쉬맵에서 검색해서 도출하도록 하자.

 

해쉬맵과 큐를 사용하면 쉽게 해결이 가능하다. 굳이 정렬큐를 사용하지 않아도, 모든 노드의 거리는 1 임으로, 가장 최근에 적립된 큐 데이터를 기준으로 사용하면 된다.

---

첫 번째 시도

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

using namespace std;

struct Con
{
    bool operator()(const vector<int>& input1, const vector<int>& input2)
    {
        return input1[1] > input2[1];
    }
};

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer;
    unordered_map<int, vector<int>> lines;

    for (auto& road : roads)
    {
        lines[road[0]].push_back(road[1]);
        lines[road[1]].push_back(road[0]);
    }

    for (auto& def : sources)
    {
        priority_queue<vector<int>, vector<vector<int>>, Con> qu;
        unordered_map<string, int> Moved;
        vector<int> start(2);
        start[0] = def;
        start[1] = 0;
        qu.push(start);

        while (qu.top()[0]!= destination && qu.size() > 0)
        {
            vector<int> now = qu.top();
            qu.pop();

            
            for (auto& next : lines[now[0]])
            {
                string key;
                key.push_back(next);
                key.push_back(now[0]);
                if ((Moved.count(key) > 0 && Moved[key] > now[1] + 1) ||
                    Moved.count(key) <= 0)
                {
                    Moved[key] = now[1] + 1;
                    vector<int> Def(2);
                    Def[0] = next;
                    Def[1] = now[1] + 1;
                    qu.push(Def);
                }
            }
            
        }
        
        if(qu.size() == 0)
            answer.push_back(-1);
        else
            answer.push_back(qu.top()[1]);
    }
    return answer;
}

실패

 

중첩데이터를 피하기 위해, 방문했던 노드를전부 제외하는 코드를 추가하였고 우선순위 큐를 사용해서 거리별 측정데이터를 분간하였다.

 

그러나, 거리별 측정데이터는 어차피 모든 노드의 거리가 1 이기 때문에 가장 최근의 노드먼저 탐색하면 해결되는 문제라. 굳이 정렬을 하면서 리소스를 소모할 필요가 없었고,

 

방문했던 노드를 전부 제외하는 코드의 경우에는 방문했던 노드를 전부 제외하면서 발생하는, 중간노드를 거치게되는 경우 탐색이 불가능해지는 상황이 발생했다.

1번 이후 2번을 탐색하면 탐색이 실패한다.

위의 경우를 두가지 고려하지 못해서 실패

---

두 번째 시도

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

using namespace std;

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer;
    unordered_map<int, vector<int>> lines;
    for (auto& road : roads)
    {
        lines[road[0]].push_back(road[1]);
        lines[road[1]].push_back(road[0]);
    }

    for (auto& def : sources)
    {
        queue<vector<int>> qu;
        qu.push({def, 0});

        int back = def;
        while (qu.front()[0]!= destination && qu.size() > 0)
        {
            vector<int> now = qu.front();
            qu.pop();
            for (auto& next : lines[now[0]])
                if(next != def)
                    qu.push({next, now[1] + 1});

            def = now[0];
        }
        if (qu.size() == 0)
            answer.push_back(-1);
        else
            answer.push_back(qu.front()[1]);
    }
    return answer;
}

실패

 

가능한 쓿모없는 연산데이터를 전부 날리고, 효율적으로 작성하였다.

 

그러나, 중복으로 탐색이 이루어지는 경우 시간초과가 나타나기 때문에, 중복연산으로 인한 시간초과를 피할 수 없었다.

 

중복데이터를 처리하는 과정을 생각해야한다.

1번에서 2번으로 이동했을 때, 2번에서 두번 검색처리가 이루어지는 경우,

---

세 번째 시도

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

using namespace std;

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer;
    unordered_map<int, vector<int>> lines;
    unordered_map<int, int> visited;
    visited[destination] = 0;
    
    for (auto& road : roads)
    {
        lines[road[0]].push_back(road[1]);
        lines[road[1]].push_back(road[0]);
    }

    queue<vector<int>> movePoints;
    movePoints.push({ destination, 0 });

    while (movePoints.size() > 0)
    {
        vector<int>& front = movePoints.front();
        for (auto& next : lines[front[0]])
        {
            if (visited.count(next) <= 0) {
                visited[next] = front[1] + 1;
                movePoints.push({ next, front[1] + 1 });
            }
        }
        movePoints.pop();
    }

    for (auto& def : sources) {
        if (visited.count(def) <= 0)
            answer.emplace_back(-1);
        else
            answer.emplace_back(visited[def]);
    }
    return answer;
}

성공

 

그냥, 목표지점부터 탐색을 진행하였다. 목표지점부터 진행한 탐색으로 인하여, 전체탐색 이후에 굳이 더 탐색할 필요가 없는 노드는 탐색하지 않음으로, 탐색시간이 O(n)이 된다.그렇기 때문에, 더 효율적으로 탐색할 수 있다.