[프로그래머스] 가장 먼 노드

접근 방법 : BFS
최단 최단 최단경로 나오면 무조건 BFS(다익스트라) 생각하자!!
기존 방문 처리를 bool형으로 했는데, 다른 풀이를 보면 더 효율적으로 처리하여 신기했다.

from collections import defaultdict, deque
graph_dict = defaultdict(list)
result_dict = defaultdict(list)
node_list = deque([])
max_cnt = 0

def bfs(v, curr, cnt):
    global max_cnt
    node_list.append([curr, cnt])
    
    while node_list:
        t_cur, t_cnt = node_list.popleft()
        
        for e in graph_dict[t_cur]:
            if not v[e]:
                v[e] = True
                result_dict[t_cnt + 1].append(e)
                node_list.append([e, t_cnt + 1])
                max_cnt = max(max_cnt, t_cnt + 1)
    return

def solution(n, edge):
    answer = 0
    visited = [False] * (n + 1)
    
    for e in edge:
        graph_dict[e[0]].append(e[1])
        graph_dict[e[1]].append(e[0])
    
    visited[1] = True
    bfs(visited, 1, 0)
    
    answer = len(result_dict[max_cnt])
    return answer

다른 사람 풀이

from collections import deque, defaultdict

def solution(n, edge):
    routes = defaultdict(list)
    for e1, e2 in edge:
        routes[e1].append(e2)
        routes[e2].append(e1)
        
    q = deque([[1, 0]]) 
    
    check = [-1]*(n+1)
    
    while q:
        index, depth = q.popleft()
        check[index] = depth
        for i in routes[index]:
            if check[i]== -1:
                check[i] = 0
                q.append([i, depth+1])
    return check.count(max(check))