(Python) - 프로그래머스 : 가장 먼 노드

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

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

 

• 해설:

그래프 vertex사이의 간선정보가 주어질 때  1번째 노드에서 가장 멀리 떨어져있는 노드가 몇 개인지를 return하면 된다.

 

 

 

 

• 풀이:

vertex사이의 간선정보를 통해 n개의 노드 사이에 연결정보를 담은 list를 새로 만든다. 

이 list를 BFS로 전체탐색하여 이미 탐색한 node의 정보를 1번노드로부터의 거리로 초기화시켜준다.  모든 탐색을 마치고 거리정보가 담긴 list의 max을 카운팅해주면 된다.

 

 

 

 

from collections import deque
 
def solution(n, edge):
    c = [-1] * (n+1)
    v = [[] for _ in range(n+1)]
    c[1] = 0
    for a,b in edge:
        v[a].append(b)
        v[b].append(a)
    queue = deque()
    queue.append(1)
    while queue:
        x = queue.popleft()
        for i in v[x]:
            if c[i] == -1:
                c[i] = c[x] + 1
                queue.append(i)
    return c.count(max(c))