[그래프] 가장 먼 노드

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

문제 풀이

• 1번 노드에서 출발 해서 각 노드들에 최단 경로로 도착하는데 그 중에 가장 멀리 떨어진 노드들의 갯수를 출력하는 문제
• 다익스트라로 풀었는데 노드 갯수만 적었다면 bfs dfs도 가능할듯?
•  

소스 코드

import heapq
INF = int(1e9)

def solution(n, edge):
    answer = 0
    gr = [[]for i in range(n+1)]
    dit = [INF]*(n+1)
    dit[1]=0
    q = []
    for s,e in edge:
        gr[s].append(e)
        gr[e].append(s)
    heapq.heappush(q,(0,1))
    m=0
    while(q):
        dd, cur = heapq.heappop(q)
        for next in gr[cur]:
            d = dd+1
            if dit[next]>d:
                dit[next]=d
                heapq.heappush(q,(d,next))
                m=max(m,d)

    return dit.count(m)

print(solution(6,[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]))