[프로그래머스] level 3 - 가장 먼 노드, C++

https://programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

본 문제의 자세한 설명은 링크를 참고하길 바란다.

1. vector를 인접 리스트로 만들고 BFS 탐색을 한다. (chk 배열을 통해 1번만 방문하도록 한다.)
2. 1에서 떨어진 길이를 기준으로 배열의 값을 증가 시킨다.
3. 가장 멀리 떨어진 길이를 구하고 그 길이의 배열값을 return한다.

#include <string>
#include <vector>
#include <queue>
#include <iostream>
 
using namespace std;
 
int d[20001];
bool chk[20001];
 
int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    vector<int> v[20001];
    for (int i = 0; i < edge.size(); i++) {
        int x = edge[i][0];
        int y = edge[i][1];
        v[x].push_back(y);
        v[y].push_back(x);
    }
    queue<pair<int, int>> q;
    q.push(make_pair(1, 0));
    chk[1] = true;
    
    while (!q.empty()) {
        int node = q.front().first;
        int cnt = q.front().second;
        q.pop();
        for (int k = 0; k < v[node].size(); k++) {
            int next = v[node][k];
            if (chk[next]) continue;
            chk[next] = true;
            d[cnt+1] += 1;
            q.push(make_pair(next, cnt+1));
            answer = cnt+1;
        }
    }
    
    return d[answer];
}