[1일 1알고] 부대 복귀

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

프로그래머스

 

간단한 BFS문제입니다.

 

그런데 약간 생각을 잘못한 부분이 있었네요

 

보면 sources들 에서 destination까지 가는 거리를 각각 측정하는 것입니다.

처음에는 source마다 bfs를 돌려 dest 까지의 거리를 측정했는데, 통과는 했지만 몇몇 test에서 많은 시간이 소요되었습니다.

// 지역은 유일한 번호로 구분
// 최단시간 복귀
//
int bfs(int n, int src, vector<vector<int>>& arr, int dest)
{
    queue<pair<int, int>> q;
    q.push({ src, 0 });
    vector<bool> visited(n + 1, false);
    visited[src] = true;
    int res = -1;
    while (!q.empty())
    {
        auto poll = q.front();
        q.pop();
        if (poll.first == dest)
        {
            res = poll.second;
            break;
        }

        for (auto next : arr[poll.first])
        {
            if (!visited[next])
            {
                visited[next] = true;
                q.push({ next, poll.second + 1 });
            }
        }
    }
    return res;
}

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer;

    vector<vector<int>> arr(n + 1);

    for (auto road : roads)
    {
        arr[road[0]].push_back(road[1]);
        arr[road[1]].push_back(road[0]);
    }

    for (auto src : sources)
    {
        int res = bfs(n, src, arr, destination);
        answer.push_back(res);
    }

    return answer;
}

---

생각해보니 굳이 source마다 dest까지의 거리를 구할 필요없이 dest에서 전체를 대상으로 bfs를 한번 돌리면 모든 거리가 측정됩니다.

int bfs(int n, int src, vector<vector<int>>& arr, vector<int>& dist)
{
    queue<pair<int, int>> q;
    q.push({ src, 0 });
    vector<bool> visited(n + 1, false);
    visited[src] = true;
    int res = -1;
    dist[src] = 0;
    while (!q.empty())
    {
        auto poll = q.front();
        q.pop();

        for (auto next : arr[poll.first])
        {
            if (!visited[next])
            {
                visited[next] = true;
                dist[next] = poll.second + 1;
                q.push({ next, poll.second + 1 });
            }
        }
    }
    return res;
}

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer;

    vector<vector<int>> arr(n + 1);

    for (auto road : roads)
    {
        arr[road[0]].push_back(road[1]);
        arr[road[1]].push_back(road[0]);
    }

    vector<int> dist(n + 1, -1);
    int res = bfs(n, destination, arr, dist);


    for (auto src : sources)
    {
        answer.push_back(dist[src]);
    }

    return answer;
}

변경한 코드입니다.

이전 코드에서 빠르게 고쳐 사용하지 않는 return값 등의 필요없는 계산들이 남아있지만 아무튼 이전과는 다르게 큰 n에서도 빠른 성능을 보여줬습니다.