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

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

가장 먼 노드

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

문제 단순화

• 노드가 갯수 n, 간선 정보 vertex가 있다.
• 1번 노드부터 다른 노드까지 최단 경로로 이동했을 때, 가장 멀리 떨어진 노드의 개수를 리턴한다.

문제풀이

• 간선 정보 이용하여, 각 노드에 연결된 노드들을 정의한다.
• 1번 노드부터 BFS 탐색을 진행한다.
• 탐색을 진행할 때, 1번 노드부터로의 거리를 같이 저장한다.
• 새로운 노드를 발견할 때, 부모노드의 거리에 1을 더하여 저장한다.
• 저장한 거리의 최댓값의 개수를 리턴한다.

코드

from collections import deque

def solution(n, edge):
    answer = 0

    nodes = [[] for _ in range(n+1)]
    for e in edge:
        nodes[e[0]].append(e[1])
        nodes[e[1]].append(e[0])

    dist_list = []

    dq = deque([(1,0)])
    visited = [False for _ in range(n+1)]
    visited[1] = True

    while dq:
        idx, dist = dq.popleft()
        for node in nodes[idx]:
            if not visited[node]:
                visited[node] = True
                dq.append((node,dist+1))
                dist_list.append(dist+1)

    answer = dist_list.count(max(dist_list))

    return answer