[Programmers] Lv3. 가장 먼 노드 | C++

🔗문제 보러가기

프로그래머스

 

🧑‍💻 풀이 과정

 

처음엔 다익스트라(Dijkstra) 알고리즘을 먼저 떠올렸는데, BFS로도 간단하게 풀 수 있겠단 생각이 들어 BFS로 풀었습니다. 알고리즘은 다음과 같습니다.

 

1. 행 번호는 노드의 번호, 열 번호는 행 번호 노드와 연결된 다른 노드들의 번호로 이루어진 2차원 배열을 선언한다.
2. 1번 노드를 방문 처리 후 Queue에 넣고, BFS 탐색을 시작한다.
3. Queue에서 노드(source)를 꺼낸 후, 해당 노드와 연결된 다른 노드들을 방문 처리 후 Queue에 넣는다.
4. 이 때, source 노드와 연결된 다른 노드들의 거리값은 source 노드 거리값 + 1로 갱신한다.
5. 갱신된 거리값을 별도의 배열에 담는다.
6. 위 과정을 Queue가 빌 때까지 반복한다.
7. 거리값이 저장된 배열을 내림차순 정렬 후, 첫 번째 값의 개수를 세어 리턴한다.

 

✏️소스 코드 및 결과

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct Node
{
    vector<int> otherNodes;
    int _distance = 0;
};

int BFS(vector<Node>& nodes, const int n, int v)
{
    vector<bool> visited(n + 1, false);
    queue<int> next;
    next.push(v);
    visited[v] = true;

    vector<int> candidates;
    candidates.reserve(n);

    while (!next.empty())
    {
        v = next.front();
        next.pop();

        for (const auto& otherNode : nodes[v].otherNodes)
        {
            if (visited[otherNode])
                continue;

            visited[otherNode] = true;
            int nextDistance = nodes[v]._distance + 1;
            
            nodes[otherNode]._distance = nextDistance;
            candidates.push_back(nextDistance);
            next.push(otherNode);
        }
    }

    sort(candidates.begin(), candidates.end(), greater<int>());
    return std::count(candidates.begin(), candidates.end(), candidates[0]);
}

int solution(int n, vector<vector<int>> edge) {
    // 1. 노드 별로 간선 정보 정리하기
    vector<Node> nodes(n + 1);
    for (const auto& e : edge)
    {
        int start = e[0], dest = e[1];
        nodes[start].otherNodes.emplace_back(dest);
        nodes[dest].otherNodes.emplace_back(start);
    }

    // 2. BFS
    int answer = BFS(nodes, n, 1);
    return answer;
}