문제 풀이
[Python] 가장 먼 노드
_tera_
2022. 9. 28. 21:42
https://school.programmers.co.kr/learn/courses/30/lessons/49189
큐를 이용한 bfs 문제
q에 있는 노드들을 방문한 뒤 가장 마지막에 남는 노드들 즉, 1에서 가장 먼 리프노드들을 출력한다
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
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
|
cs |