[HackerRank] Breadth First Search: Shortest Reach

HackerRank 알고리즘 문제 풀이

분류

Practice > Algorithms > Graph Theory

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

풀이

무향 그래프를 나타내는 간선의 연결 정보와 시작점이 주어질 때, 시작점에서 각각의 노드를 순회하는데 얼마의 비용이 필요한지 구하는 문제이다. (한 번 이동하는데 드는 비용은 6)

우선 매개변수로 edges의 연결정보를 adj라는 이차원 벡터로 재구성하고 너비 우선 탐색(BFS)을 하면서 시작점 노드 s를 기준으로 1번 노드부터 n번 노드까지 이동하는데 얼마나 소요되는지 구하였다.

dist 벡터가 -1로 초기화 되어있으므로 BFS를 모두 수행하고 나서도 -1로 되어있는 부분은 시작점 s에서 출발했을 때 도착할 수 없는 위치를 말한다.

시작점 노드(s)는 정답에서 제외되어야 하므로 i == s인 경우를 제외한 모든 비용을 순서대로 ans 벡터에 추가하였다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

// Complete the bfs function below.
vector<int> bfs(int n, int m, vector<vector<int>> edges, int s) {
    vector<int> dist(n + 1, -1), ans;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i != m; ++i) {
        int& u = edges[i][0];
        int& v = edges[i][1];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<bool> visited(n + 1);
    queue<int> q;
    q.push(s);
    visited[s] = true;
    dist[s] = 0;
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (const int& next : adj[now]) {
            if (visited[next]) continue;
            visited[next] = true;
            q.push(next);
            dist[next] = dist[now] + 6;
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (i == s) continue;
        ans.push_back(dist[i]);
    }
    return ans;
}