프로그래머스 문제 - 부대복귀

프로그래머스 부대복귀 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

강철부대의 각 부대원들이 여러 지역에 뿔뿔이 흩어져 특수 임무를 수행 중입니다.
여러 지역에 있는 부대원들은 정해진 지역으로 움직여야 합니다.
총 지역의 수, 지역 간의 길, 부대원들의 있는 지역 위치, 모이는 위치가 배열 및 값으로 주어지며 부대원들이 모이는 위치로 갈 수 있는 최단 거리들을 순서대로 구해야합니다. 모이지 못하는 부대원은 -1로 표현해줍니다.

문제 풀이

문제를 읽어보면 각 부대원들을 기준으로 목표까지 갈 수 있는지 전부 확인해보면 되는 문제입니다.
하지만 역으로 바라보게 되면 모이는 위치부터 시작하여 갈 수 있는 모든 길을 확인해보면 각 부대원들의 최단 거리를 빠르게 구할 수 있게 됩니다.

현재 있는 지역과 부대원들이 있는 거리를 빠르게 찾기 위해 해쉬를 사용하여 컨테이너인 map을 사용하였으며 넓은 범위를 아래로 차례대로 내려가며 최단 거리를 찾아야 하기 때문에 BFS를 사용하여 문제를 해결할 수 있습니다.

탐색을 마친 후 등록된 값들을 sources값 순서대로 넣어준 후 return하면 됩니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer;
    vector<int> area[n+1];
    queue<int> q;
    vector<int> visit(n+1, 0);
    map<int, int> sourcesMap;
    
    //간선을 배열에 등록
    for(vector<int> v : roads)
    {
        area[v[0]].push_back(v[1]);
        area[v[1]].push_back(v[0]);
    }
    //거리를 찾아야하는 값들 해쉬값으로 저장
    for(int n : sources)
    {
        sourcesMap.emplace(make_pair(n, -1));
    }
    
    int cnt = 0;
    q.push(destination);
    map<int, int>::iterator iter;
    while(!q.empty())
    {
        int qSize = q.size();
        for(int i = 0; i < qSize; i++)
        {
            int cur = q.front();
            q.pop();
            
            //찾아야하는 값을 찾으면 거리 등록
            iter = sourcesMap.find(cur);
            if(iter != sourcesMap.end())
            {
                if(iter->second > cnt || iter->second == -1)
                {
                    iter->second = cnt;
                }
            }
            
            //이미 지나간 길은 체크
            visit[cur] = 1;
            for(int n : area[cur])
            {
                if(visit[n] == 0)
                {
                    q.push(n);
                }
            }
        }
        cnt++;
    }
    //sources순서대로 값 등록
    for(int s : sources)
    {
        answer.push_back(sourcesMap[s]);
    }
    
    return answer;
}

출저

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