[해커랭크] Breadth First Search: Shortest Reach (C++)

문제 링크: www.hackerrank.com/challenges/bfsshortreach/problem

Breadth First Search: Shortest Reach | HackerRank

1. 주의할 점

- 각 쿼리마다 사용한 전역변수를 잘 초기화한다

 

2. 구현

- 시작점에서 다른 Node까지의 거리를 저장하는 Dist[] 배열과 각 Node에 연결된 간선들에 대한 정보를 저장하는 V[] 벡터를 초기화한다 

- 넘겨 받은 간선들에 대한 정보를 V[]배열에 저장한다

- 시작점을 Queue에 넣은 이후, BFS를 통해 다음 Node의 Dist가 현재까지의 Dist + 1보다 크다면 갱신하고 Queue에 추가한다

- Result 벡터에는 결과를 저장하며, 시작점을 제외한 모든 Node에 대해 Dist[]의 값이 초기값인 MAX가 아니면 Dist값*6을 저장하고, 초기값이라면 -1을 저장한다

 

#define MAX 987654321
#include <bits/stdc++.h>

using namespace std;
vector<string> split_string(string);
struct info{
    int idx,val;
};
info tmp;
int dist[1001];
vector<int> v[1001];
// Complete the bfs function below.
vector<int> bfs(int n, int m, vector<vector<int>> edges, int s) {
    //초기화
    vector<int> result;
    for(int i=1;i<=n;i++){
        dist[i]=MAX;
        v[i].clear();
    }
    
    for(int i=0;i<m;i++){
        int a = edges[i][0];
        int b = edges[i][1];
        v[a].push_back(b);
        v[b].push_back(a);
    }
    queue<info> q;
    tmp.idx = s;
    tmp.val=0;
    q.push(tmp);
    dist[s] = 0;
    while(!q.empty()){
        int cidx = q.front().idx;
        int cv = q.front().val;
        q.pop();
        for(int i=0;i<v[cidx].size();i++){
            int next = v[cidx][i];
            if(dist[next] > cv+1){
                dist[next]=cv+1;
                tmp.idx = next;
                tmp.val = cv+1;
                q.push(tmp);
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(i==s) continue;
        if(dist[i]==MAX) result.push_back(-1);
        else result.push_back(6*dist[i]);
    }
    return result;
}