프로그래머스 - LV3. 가장 먼 노드

문제

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

프로그래머스

 

코드

BFS 이용

from collections import deque

def solution(n, edge):
    shortest_path = [1]+[0 for _ in range(n-1)]
    graph = [[] for _ in range(n)]
    for e in edge:
        graph[e[0]-1].append(e[1]-1)
        graph[e[1]-1].append(e[0]-1)
    print(graph)
    
    #bfs => 큐로 구현
    queue = deque([0])
    while queue:
        v = queue.popleft()
        for w in graph[v]:
            print('queue', queue)
            print(shortest_path)
            if shortest_path[w] == 0:
                queue.append(w)
                shortest_path[w] += shortest_path[v]+1
    
    return shortest_path.count(max(shortest_path))

입력값 〉	6, [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]
기댓값 〉	3
실행 결과 〉	테스트를 통과하였습니다.
출력 〉	[[2, 1], [2, 0, 3, 4], [5, 3, 1, 0], [2, 1], [1], [2]] deque([]) [1, 0, 0, 0, 0, 0] deque([2]) [1, 0, 2, 0, 0, 0] deque([1]) [1, 2, 2, 0, 0, 0] deque([1, 5]) [1, 2, 2, 0, 0, 3] deque([1, 5, 3]) [1, 2, 2, 3, 0, 3] deque([1, 5, 3]) [1, 2, 2, 3, 0, 3] deque([5, 3]) [1, 2, 2, 3, 0, 3] deque([5, 3]) [1, 2, 2, 3, 0, 3] deque([5, 3]) [1, 2, 2, 3, 0, 3] deque([5, 3]) [1, 2, 2, 3, 0, 3] deque([3, 4]) [1, 2, 2, 3, 3, 3] deque([4]) [1, 2, 2, 3, 3, 3] deque([4]) [1, 2, 2, 3, 3, 3] deque([]) [1, 2, 2, 3, 3, 3]