[프로그래머스 Lv3, python] - 가장 먼 노드

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

프로그래머스

# 내 풀이
from collections import defaultdict,deque

def solution(n, edge):
    answer = 0
    
    depth = defaultdict(int) # 깊이 : 몇개
    depth[1] = 1
    
    nodes = defaultdict(list)
    for a, b in edge:
        nodes[a].append(b)
        nodes[b].append(a)
    
    visited = [False]*(n+1)
    visited[1] = True
    queue = deque([(1,1)]) # 노드번호, depth
    
    while queue:
        node, dep = queue.popleft()
        
        for x in nodes[node]:
            if not visited[x]:
                queue.append((x,dep+1))
                depth[dep+1] += 1 # 해당 깊이 개수 + 1
                visited[x] = True
    return depth[len(depth)]

from collections import defaultdict, deque

def solution(n, edge):
    nodes = defaultdict(list)

    # 그래프 저장
    for a, b in edge:
        nodes[a].append(b)
        nodes[b].append(a)

    # 각 노드까지 거리 저장
    depth = [-1] * (n + 1)
    depth[1] = 0

    queue = deque([1])

    # BFS
    while queue:
        node = queue.popleft()

        for x in nodes[node]:
            if depth[x] == -1:   # 방문 안 한 경우
                depth[x] = depth[node] + 1
                queue.append(x)

    max_depth = max(depth)

    return depth.count(max_depth)