프로그래머스 - 가장 먼 노드

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

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

 

1. 유형

그래프

 

2. 풀이

1) 인접리스트 생성

2) BFS돌리면서 거리까지 저장. [노드, 이동한 거리] 형태로 큐에 저장

3) 가장 먼 노드의 갯수 카운트

 

3. 코드

from collections import deque
def solution(n, edge):
    answer = 0
    lists= [ [] for _ in range(n+1)]
    dists = [ 0 for _ in range(n+1)]
    for u,v in edge:
        lists[u].append(v)
        lists[v].append(u)
    q = deque()
    q.append([1, 0])
    dists[1] = -1
    while q:
        node, dist = q.popleft()
        for next_node in lists[node]:
            if dists[next_node] == 0:
                dists[next_node] = dist +1
                q.append([next_node, dists[next_node]])
    maxval = max(dists)
    for el in dists:
        answer = answer+1 if el==maxval else answer
    return answer