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

문제

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

프로그래머스

문제풀이

BFS문제이다. 목적지가 나와있으므로 목적지를 시작으로 모든 다리를 건너 갈 수 있는 경우를 탐색했다.

다리의 정보가 담긴 roads벡터에서는 {1, 2}, {2, 3} 이런식으로 나와있어 따로 road벡터로 탐색시간을 줄이고자 한다.

road벡터에는 road[1]에는 1과 연결된 다리들을, road[2]에는 2와 연결된 다리들을 이런식으로 road[n]에는 n과 연결된 다리의 정보가 담긴다. 다리는 양방향이므로 각각 서로 연결된 다리 번호를 저장한다.

 

visit벡터는 갈 수 없는 곳인 경우 -1을 출력해야하므로 -1로 초기화를 했다.

그 외의 경우는 몇번만에 갔는지를 저장한다.

 

    while (!q.empty()) {
        num = q.front()[0];
        cnt = q.front()[1];
        q.pop();

        for (idx = 0; idx < road[num].size(); ++idx) {
            int next = road[num][idx];
            if (visit[next] == -1) {
                visit[next] = cnt + 1;
                q.push({ next, cnt + 1 });
            }
        }
    }

목적지부터 큐에 넣고 시작한다.

num은 현재 위치이고 road벡터를 통해 갈 수 있는 다리들을 찾아본다.

다리와 연결된 곳이 -1일 때만 (최초로 갈 때만) visit[next]의 값을 바꾸고 큐에 push한다.

이 작업들을 큐가 비워질때까지 반복한다.

 

    for (idx = 0; idx < sources.size(); ++idx) {
        answer[idx] = visit[sources[idx]];
    }

반복문이 종료됐으면 결과를 내보내야 하므로 아군의 위치가 담겨있는 sources벡터를 돌면서 answer에 방문 값을 저장한다.

 

코드

#include <string>
#include <vector>
#include <queue>
using namespace std;

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    int idx(0), num(0), cnt(0);
    queue<vector<int>>q;
    vector<int>visit(n + 1, -1);
    vector<int>answer(sources.size(), 0);    
    vector<vector<int>>road(n + 1, vector<int>(0, 0));

    for (idx = 0; idx < roads.size(); ++idx) {
        road[roads[idx][0]].push_back(roads[idx][1]);
        road[roads[idx][1]].push_back(roads[idx][0]);
    }

    q.push({ destination,0 });
    visit[destination] = 0;

    while (!q.empty()) {
        num = q.front()[0];
        cnt = q.front()[1];
        q.pop();

        for (idx = 0; idx < road[num].size(); ++idx) {
            int next = road[num][idx];
            if (visit[next] == -1) {
                visit[next] = cnt + 1;
                q.push({ next, cnt + 1 });
            }
        }
    }
    for (idx = 0; idx < sources.size(); ++idx) {
        answer[idx] = visit[sources[idx]];
    }

    return answer;
}