728x90


너비우선탐색(BFS) 기법을 사용하여 1번 노드에서 각 노드까지의 최단 경로를 계산하여 visited에 딕셔너리 형태로 저장합니다. 그 후 가장 먼 노드의 경로와 같은 값을 갖고 있는 노드를 세서 반환합니다.
솔루션
from collections import defaultdict,deque
def solution(n, edge):
answer = 0
graph = defaultdict(list)
for a,b in edge:
graph[a].append(b)
graph[b].append(a)
visited= defaultdict(int)
queue = deque([[1,0]])
# BFS
while queue:
current_node,num = queue.popleft()
if current_node not in visited:
visited[current_node] =num
for adj_node in graph[current_node]:
if adj_node not in visited:
queue.append([adj_node,num+1])
# 가장 먼 노드
distance = sorted(visited.values(), reverse=True)
longest = distance[0]
return distance.count(longest)
728x90
'알고리즘' 카테고리의 다른 글
[python 스택] 짝지어 제거하기 - 프로그래머스 (0) | 2021.06.18 |
---|---|
[python 그래프] 순위 알고리즘 - 프로그래머스 (0) | 2021.06.09 |
[python 그리디(탐욕법)] 구명보트 - 프로그래머스 (0) | 2021.06.04 |
[python 그리드] 큰 수 만들기 -프로그래머스 (0) | 2021.06.03 |
[python 이분 탐색] 입국심사 프로그래머스 (0) | 2021.06.02 |