가장 먼 노드 (feat. 프로그래머스, 49189번)

가장 먼 노드
https://programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

반응형

// woohyeon.kim
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    vector<int> distance(n + 1);
    queue<int> q;
    q.push(1);
    distance[1] = 1;
    while(!q.empty())
    {
        auto node = q.front();
        q.pop();
        for(const auto& edge_at : edge)
        {
            if(node != edge_at[0] && node != edge_at[1])
                continue;
                
            auto other_node = 0;
            if(node == edge_at[0])
                other_node = edge_at[1];
            else
                other_node = edge_at[0];
            
            if(distance[node] == 0 || distance[other_node] != 0)
                continue;
            distance[other_node] = distance[node] + 1;
            q.push(other_node);
        }
    }
    int answer = 0;
    auto max_distance = *max_element(distance.begin(), distance.end());
    for(const auto& dist : distance)
    {
        if(max_distance == dist)
            ++answer;
    }
    return answer;
}
// *&)*@*

경로를 구하는 방법은 bfs로 간단하게 표현 가능합니다.

경로는 결국 모두 이어지기 때문에 첫 노드만 입력하면 됩니다.

​

질문하기에서 얻은 팁은 distance 를 가지고 가야한다는 의견이었고, 그에 따라 부모와 자식간 거리를 distance에 입력하면 됩니다.

distance의 배열 번호가 결국 노드의 번호가 되겠고, 동일한 레벨간 간선이 있더라도

if(distance[node] == 0 || distance[other_node] != 0) 중 distance[other_node] != 0 에 의해 무시됩니다.

왜냐면 1번을 부모로 갖는 모든 자식의 노드에 distance가 선 입력되기 때문입니다.