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

코딩테스트 연습 - 부대복귀 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

위 문제는 BFS를 이용해 푸는 최단거리 구하기 문제입니다.

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
//bfs
vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> map[100001];
    vector<int> count(n + 1, -1);
    vector<int> answer;
    queue<pair<int,int>> q; //queue는 pair로 두 값을 갖도록 해야함(현재 위치, 현재 카운트)
    for(int i = 0; i <roads.size(); i++)
    {
        map[roads[i][0]].push_back(roads[i][1]);
        map[roads[i][1]].push_back(roads[i][0]);
    }//양방향 연결해주어야 하므로
    q.push({destination, 0});     //목적지 방향부터 시작
    count[destination] = 0;
    while(!q.empty())
    {
        int curPos = q.front().first; //queue가장 좌측의 첫 요소(position)
        int curCount = q.front().second; //queue가장 우측의 두번째 요소(count)
        q.pop();
        for(auto nextPos: map[curPos])//이런식으로 해줘야 map[curPos]에 쌓인 벡터요호들 하나씩 출력가능
        {
            if(count[nextPos] == -1 || count[nextPos] > curCount + 1) //방문한 적이 없거나 원래 카운트보다 작을 때
            {
                q.push({nextPos, curCount + 1});
                count[nextPos] = curCount + 1;   
            }
        }
    }
    for (auto src : sources) answer.push_back(count[src]);
    return answer;
}

키포인트

1.벡터 배열을 이용한 간선 연결

vector<int> map[100001] => 이런식으로 하면 100001개짜리 벡터 배열을 만들 수 있습니다.

양방향으로 연결되어야하므로 

    for(int i = 0; i <roads.size(); i++)
    {
        map[roads[i][0]].push_back(roads[i][1]);
        map[roads[i][1]].push_back(roads[i][0]);
    }

이런식으로 연결해주어야 합니다.

 

2.position과 depth를 담는 queue생성

queue<pair<int, int>> q 이런식으로 하고

q.push({pos, 0});이런 식으로 초기값 설정이 가능합니다.

 

while문 실행 전에는 무조건 초기값 설정과 q.push가 이루어져야 합니다.

 

3.q에 들어있는 첫번째 값부터 시작하여 while문에서 for문으로 연결된 값 돌기

curPos는 처음 지정해준 포지션이므로 map[curPos]를 for문으로 돌면 모든 연결된 값에 대하여 너비우선 탐색이 가능해집니다.

 

4.방문한적 없거나 기존 depth보다 작은지 판단

방문한 적 없거나 기존 깊이보다 작으면 push할 수 있는 조건에 해당합니다.

이 때 count + 1해서 push해줍니다.

count라는 vector를 따로 만들어서 초기값 -1에서 갱신해줘서 second와 같은 값을 저장해주는 이유는

queue는 인덱스 참조가 불가능하기 떄문입니다.