가장 먼 노드

설명

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

# BFS? 모든 노드 다 탐색하고 길이 가장 긴 애들 출력
# 근데 이거 20000에 50000인데 가능?
from collections import deque

def solution(n, edge):
    answer = 0
    dq = deque()
    visit = [0]*(n+1)
    edgeList = [[] for _ in range(n+1)]
    for s, d in edge:
        edgeList[s].append(d)
        edgeList[d].append(s)
        # 양방향 간선
    visit[1] = 1
    dq.append(1)
    while dq:
        node = dq.popleft()
        for k in edgeList[node]:
            if visit[k] == 0:
                visit[k] = visit[node]+1
                dq.append(k)
    
    answer = visit.count(max(visit))
    return answer

• 제한사항을 보고 든 생각은 BFS로 전부 탐색하고 경로가 가장 긴 노드를 찾으면 되겠다고 생각했다.
• 근데 노드가 최대 20000개에 간선이 50000개인데 되나? 일단 해봤다.
• i번째 노드의 인접노드를 저장하는 edgeList를 선언하여 관리하자.
• 처음에 놓쳐서 틀렸던 정보는 간선은 양방향이라는 점
• 리스트 길이가 길어서 긴가민가했는데 잘 해결됐다.