[프로그래머스/파이썬] 가장 먼 노드

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

프로그래머스

그래프 문제이다

 

딱히 추가적으로 구현해야 할 건 없고, 양방향 그래프를 잘 입력받은 뒤

bfs로 탐색을 해주면 된다

 

간선에 가중치가 붙으면 다익스트라를 이용해주면 된다

from collections import deque

def solution(n, edge):
    answer = 0
    graph = [[] for _ in range(n+1)]
    visited = [False] *(n+1)
    dist = [0] * (n+1)
    q = deque()
    
    for start, end in edge:
        graph[start].append(end)
        graph[end].append(start)
    
    visited[1]=True
    dist[1] = 0
    q.append(1)

    while q:
        now = q.popleft()
        for next in graph[now]:
            cost = dist[now] + 1
            if not visited[next]:
                dist[next]=dist[now]+1
                q.append(next)
                visited[next] =True
    
    answer = dist.count(max(dist))
    return answer