[Programmers] 가장 먼 노드

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

프로그래머스

 

1. Python 

from collections import deque
def solution(n, edge):
    graph = [[] for _ in range(n)]
    for u, v in edge:
        u -= 1
        v -= 1
        graph[u].append(v)
        graph[v].append(u)
    q = deque()
    q.append((0, 0))
    visited = set()
    visited.add(0)
    ret = 0
    dist = -1
    while q:
        dist_u, u = q.popleft()
        if dist_u > dist:
            ret, dist = 0, dist_u
        ret += 1
        for v in graph[u]:
            if v not in visited:
                q.append((dist_u + 1, v))
                visited.add(v)
    return ret

 

2. C++

#include <string>
#include <vector>
#include <set>
#include <deque>

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    
	vector<vector<int>> graph (n, vector<int>());
	for (auto vec : edge) {
		int u = vec[0], v = vec[1];
		u--; v--;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	
	deque<pair<int, int>> q;
	q.push_back({0, 0});
	set<int> visited;
	visited.insert(0);
	
	int ret = 0;
	int dist = -1;
	
	while (not q.empty()) {
		auto[dist_u, u] = q.front();
		q.pop_front();
		if (dist_u > dist) {
			ret = 0;
			dist = dist_u;
		}
		ret++;
		for (int v : graph[u]) {
			if (visited.find(v) == visited.end()) {
				q.push_back({dist_u+1, v});
				visited.insert(v);
			}
		}
	}
	return ret;
}