https://school.programmers.co.kr/learn/courses/30/lessons/49189
그래프에서 1번 노드에서 최단 경로로 갔을 때 가장 멀리 떨어진 노드의 개수를 구하는 문제이다.
from collections import defaultdict
def solution(n, edge):
answer = 0
graph = defaultdict(list)
for a, b in edge:
graph[a].append(b)
graph[b].append(a)
que = []
idx = 0
que.append((1, 0))
visited = [True] * (n+1)
visited[1] = False
while idx < len(que):
now, count = que[idx]
idx += 1
for next in graph[now]:
if visited[next]:
visited[next] = False
que.append((next, count+1))
max = que[-1][1]
for idx, length in que:
if max == length:
answer+=1
return answer
BFS를 활용해서 탐색을 하는데 1번 노드의 거리는 0으로 시작해서 주변에 연결된 노드를 찾아갈 때 현재 거리에 1을 더해주었다.
가장 마지막에 추가된 노드가 가장 멀 것이라고 판단하였고 해당 거리를 기준으로 나머지 노드와 거리를 비교해서 가장 먼 곳에 있는 노드들의 개수를 구했다.