[HackerRank] Breadth First Search: Shortest Reach

vector<int> bfs(int n, int m, vector<vector<int>> arr, int start)
{
    vector<int> answer(n, -1);
    vector<bool> visited(n + 1, false);
    vector<vector<int>> numLinks(n + 1);

    for (auto nums : arr)
    {
        vector<int> linkArr;
        int firstNum = nums[0];
        int secondNum = nums[1];

        numLinks[firstNum].push_back(secondNum);
        numLinks[secondNum].push_back(firstNum);
    }

    queue<int> numQueue;
    int weight = 0;

    numQueue.push(start);
    answer[start - 1] = weight;

    while (true)
    {
        if (numQueue.size() == 0)
        {
            break;
        }

        int front = numQueue.front();
        numQueue.pop();

        auto arr = numLinks[front];
        weight = answer[front - 1] + 6;

        visited[front] = true;

        for (const auto num : arr)
        {
            if (visited[num])
            {
                continue;
            }

            visited[num] = true;
            answer[num - 1] = weight;
            numQueue.push(num);
        }
    }

    auto iter = answer.begin() + start - 1;
    answer.erase(iter);

    return answer;
}

 

bfs 를 이용해서 최단으로 각 노드에 도달할 수 있는 길을 찾아야 한다. 

방향성이 없는 그래프이기 때문에 한 개의 노드에 도달하는 길이 여러 개일 수도 있기 때문에 그 중 최단으로 도달한 거리를 bfs 탐색으로 찾아야 한다.

또한 문제 풀이의 포인트는 정답 컨테이너로 벡터를 사용해서 시간 복잡도를 최대한 줄이는 것이다.

잘못된 컨테이너를 선택해서 풀면 시간 초과가 나기 때문에 유의해야 한다.