[Python] 가장 먼 노드

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

---

큐를 이용한 bfs 문제

q에 있는 노드들을 방문한 뒤 가장 마지막에 남는 노드들 즉, 1에서 가장 먼 리프노드들을 출력한다

 

from collections import defaultdict, deque
def solution(n, edge):
    visited = [-1]*n
    dic = defaultdict(list)
    for e in edge:
        dic[e[0]].append(e[1])
        dic[e[1]].append(e[0])
    q = deque()
    q.append(1)
    visited[0] = 1
    while q:
        nodes = len(q)
        for _ in range(nodes):
            cur = q.popleft()
            for c in dic[cur]:
                if visited[c-1] == -1:
                    visited[c-1] = 0
                    q.append(c)
    return nodes