프로그래머스 Level 2 가장 먼 노드

거리와 탐색 관련된 문제이기 때문에 BFS를 사용해서 풀었다.

 

BFS 풀이 

마지막에 check_li.count(max(check_li))로 한 번에 제일 먼 노드의 개수를 구할 수 있다.

from collections import deque

def solution(N, edge):
    graph = [[] for _ in range(N+1)]
    q = deque([1])
    check_li = [-1]*(N+1)
    check_li[1] = 0
    
    for s, e in edge:
        graph[s].append(e)
        graph[e].append(s)
    
    while q:
        node = q.popleft()
        for n in graph[node]:
            if check_li[n] == -1:
                q.append(n)
                check_li[n] = check_li[node] + 1
    
    return check_li.count(max(check_li))