프로그래머스 Level 3 부대복귀

부대복귀 (프로그래머스 Level 3)

https://school.programmers.co.kr/learn/courses/30/lessons/132266

BFS 문제였는데
‘다수’의 ‘시작점’에서 ‘하나’의 목적지를 향해 가며,
그 최소 비용을 구하는 문제이다

처음에는 순수하게
‘각 시작점’에서 목적지로 가는 비용을 구하였는데
시간 초과가 발생하였다

이후, ‘플로이드 워셜’을 통하여
‘모든 노드’에 대하여 ‘최소 비용’을 구하였는데
당연하게도 시간초과가 발생하였다
(모든 부분을 도는 O(n^3)이므로)

따라서, 잠시 발상을 전환해
‘목적지’에서 ‘모든 노드’로 가는 BFS를 한 번 돌린 후,
그 결과물을 담는 쪽으로 코드를 바꾸어 통과하였다

방식은 간단하지만, 조금 생각의 전환이 필요한 문제였다

Code

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

using namespace std;

void findShortWayValue(unordered_map<int, vector<int>>& maps,const int n,vector<int>& dp, int start, int dest)
{
    queue<pair<int,int>> q;

    q.push({ start,0 });

    while (q.empty() == false)
    {
        auto p = q.front();
        q.pop();
        int now = p.first;
        int nowCost = p.second;

        for (const auto& nexts : maps[now])
        {
            if (dp[nexts] == -1)
            {
                int nextValue = nowCost + 1;
                dp[nexts] = nextValue;
                q.push({ nexts,nextValue });
            }
        }
    }
}

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

    for (auto& road : roads)
    {
        int start = road[0];
        int to = road[1];

        if (maps.find(start) == maps.end())
        {
            maps[start] = vector<int>();
        }

        maps[start].push_back(to);

        if (maps.find(to) == maps.end())
        {
            maps[to] = vector<int>();
        }

        maps[to].push_back(start);
    }

    vector<int> dp(n + 1, -1);
    dp[destination] = 0;

    findShortWayValue(maps, n, dp, destination, 1);

    for (int s : sources)
    {
        answer.push_back(dp[s]);
    }

    return answer;
}