[PG] 가장 먼 노드

문제

me

import heapq
def solution(n, edge):
    graph=[[] for _ in range(n)]

    for a,b in edge:
        graph[a-1].append((b-1,1))
        graph[b-1].append((a-1,1))
    heap=[(0,0)] # cost, index (start)
    INF=50001
    distances=[INF]*n
    distances[0]=0
    while heap:
        cost,idx = heapq.heappop(heap)
        for next_i,next_d in graph[idx]:
            if distances[next_i] > next_d+cost:
                distances[next_i]=next_d+cost
                heapq.heappush(heap,(distances[next_i],next_i))
    return distances.count(max(distances))

others

def solution(n, edge):
    graph =[  [] for _ in range(n + 1) ]
    distances = [ 0 for _ in range(n) ]
    is_visit = [False for _ in range(n)]
    queue = [0]
    is_visit[0] = True
    for (a, b) in edge:
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)

    while queue:
        i = queue.pop(0)

        for j in graph[i]:
            if is_visit[j] == False:
                is_visit[j] = True
                queue.append(j)
                distances[j] = distances[i] + 1

    distances.sort(reverse=True)
    answer = distances.count(distances[0])

    return answer

• 방문 노드 체크
• queue에 index만 저장