[프로그래머스] 가장 먼 노드 [C++][lv.3] 코딩테스트 고득점 Kit

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

프로그래머스

 

 

#문제 간단 정리

bfs를 활용해서 거리 측정

 

#문제 해결 방법

bfs를 활용해서 가장 먼 노드의 개수를 측정해 주면 된다

양방향 노드기 때문에 양방향 설정에 주의하도록 하자

그 이외에는 딱히 기본 bfs 기 때문에 주의할 건 없다.

 

#전체 코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <iostream>

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    
    vector<vector<int>> graph(n + 1);
    for ( auto e : edge) {
        graph[e[0]].push_back(e[1]);
        graph[e[1]].push_back(e[0]); 
    }
    
    vector<bool> visited(n + 1, false);
    vector<int> dist(n + 1, 0);

    queue<int> q;
    q.push(1); 

    visited[1] = true;

    int maxDist = 0;
    while (!q.empty()) {
        int now = q.front();
        q.pop();

        for (int next : graph[now]) {
            if (!visited[next]) {
                q.push(next);
                visited[next] = true;
                dist[next] = dist[now] + 1;
                maxDist = max(maxDist, dist[next]);
            }
        }
    }
    int count = 0;
    for(int i=1; i<=n; i++){
        if(dist[i] == maxDist){
            count++;
        }
    }
    
    for(int a : dist){
        cout << a << ' ';
    }

    return count;
}