프로그래머스 (C/C++) 49189 : 가장 먼 노드

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

프로그래머스

 

 

---

풀이

BFS로 탐색하여 1번 노드와 가까운 노드부터 순차적으로 탐색.

가장 먼 거리를 maxLev, 해당 거리의 노드의 개수를 maxLevCnt로 저장 후 maxLev과 같은 거리의 노드 개수를 구함

---

코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    vector<int> graph[20001];
    
    // connect nodes
    for (auto e : edge) {
        graph[e[0]].push_back(e[1]);
        graph[e[1]].push_back(e[0]);
    }
    
    int maxLev = 0, maxLevCnt = 1;
    bool visited[20001];
    queue<pair<int, int>> q;
    
    q.push({1, 1});
    visited[1] = true;
    while (!q.empty()) {
        int now = q.front().first, nowLev = q.front().second;
        q.pop();
        
        // update maxLev Info
        if (nowLev > maxLev) {
            maxLev = nowLev;
            maxLevCnt = 1;
        }
        
        else if (nowLev == maxLev)
            maxLevCnt++;
            
        for (int next : graph[now]) {
            if (visited[next]) continue;
            
            q.push({next, nowLev + 1});
            visited[next] = true;
        }
    }
    return maxLevCnt;
}