가장 먼 노드 49189

문제

접근 방법

그래프를 2차원 벡터로 만든 뒤 BFS를 하면 된다고 생각했다.

코드

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

int solution(int n, vector<vector<int>> edge)
{
    int answer = 0, depth = 0;
    vector<vector<int>> map(n + 1);
    vector<bool> isVisted(n + 1);
    queue<pair<int, int>> wait;
    for (auto e : edge)
    {
        map[e[0]].push_back(e[1]);
        map[e[1]].push_back(e[0]);
    }
    wait.push({1, 1});
    isVisted[1] = true;
    while (!wait.empty())
    {
        auto cur = wait.front();
        wait.pop();
        for (auto m : map[cur.first])
        {
            if (isVisted[m])
                continue;
            isVisted[m] = true;
            pair<int, int> next = {m, cur.second + 1};
            if (depth == next.second)
            {
                ++answer;
            }
            else if (depth < next.second)
            {
                answer = 1;
                depth = next.second;
            }
            wait.push(next);
        }
    }
    return answer;
}

풀이

깊이에 따라 answer 갱신되게끔 하였다. 길이를 갱신해두고 마지막에 반복문을 돌아서 해결하는 방법도 있을 것 같다고 생각하긴 했다. 실제로 찾아보니 다른 사람들은 그렇게 풀기도 했다.