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

 

 

문제

문제 설명

 

  

 

풀이

 

[문제 풀이]

 

처음에 문제를 보고 시작 부대를 기준으로 BFS를 각각 실행하는 문제라고 생각했다가, 어떻게 반복 횟수를 줄일 수 있을까 생각하다보니 모든 부대의 destination이 동일한 게 눈에 보였다.

 

반대로 말하면 destination에서 BFS로 갈 수 있는 모든 부대를 탐색한다면 한번의 BFS로 문제를 해결할 수 있다.

 

또한 roads에서 [a, b]가 주어지면 [b, a]가 주어지지 않듯이 중복된 정보는 주어지지 않는다고 했다.

그러므로 각 부대에서 방문할 수 있는 다른 부대 정보를 2차원 vector에 push해서 저장하면 반복의 횟수도 줄어들게 된다.

​

[아이디어 정리]

1. roads의 정보를 바탕으로 방문할 수 있는 경로를 저장한다.
2. destination을 기준으로 잡은 뒤 BFS로 방문할 수 있는 구역에 대한 최소시간을 계산한다.
3. sources에 저장된 출발지를 기준으로 destination에서 얼마나 걸리는지 return한다.

 

Code

 

 

#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>ans(n+1,-1);
    vector<bool> visited(n+1,false);
    queue<pair<int,int>> Q;
    pair<int,int> nowP;
    int node;
    vector<vector<int>> roadSet(n+1);
    for (int i=0; i<roads.size(); i++)
    {
        roadSet[roads[i][0]].push_back(roads[i][1]);
        roadSet[roads[i][1]].push_back(roads[i][0]);
    }
    ans[destination]=0, visited[destination]=true;
    Q.push(make_pair(destination,0));
    while (!Q.empty())
    {
        nowP = Q.front();
        Q.pop();
        for (int i=0; i<roadSet[nowP.first].size(); i++)
        {
            node=roadSet[nowP.first][i];
            if (!visited[node])
            {
                Q.push(make_pair(node,nowP.second+1));
                visited[node]=true;
                ans[node]=nowP.second+1;
            }
        }
    }
    vector<int> answer;
    for (int i=0; i<sources.size(); i++)
    {
        answer.push_back(ans[sources[i]]);
    }
    return answer;
}

 

---

 

sources를 기준으로 destination에 도달할 수 있는지 전부 BFS를 돌려야하나 생각했지만, destination이 전부 같아 쉽게 풀 수 있는 문제였다.

 

 

프로그래머스