[프로그래머스] 가장 먼 노드

programmers.co.kr/learn/courses/30/lessons/49189

코딩테스트 연습 - 가장 먼 노드

 

from collections import deque

def solution(n, edges):
    visited=[False]*(n+1)
    answer=[int(1e9)]*(n+1)
    info=[[] for _ in range(n+1)]
    for edge in edges:
        info[edge[0]].append(edge[1])
        info[edge[1]].append(edge[0])

    def bfs(v):
        q=deque()
        count=1
        visited[v]=True
        answer[v]=0
        for a in info[v]:
            q.append((a,count))

        while q:
            a,cnt=q.popleft()
            if visited[a]==True:
                continue
            else:
                visited[a]=True
                answer[a]=min(answer[a],cnt)
                for i in info[a]:
                    q.append((i,cnt+1))


    bfs(1)
    max_v=max(answer[1:])
    max_count=answer.count(max_v)

    return max_count