[프로그래머스-Lv3] 가장 먼 노드 / Python

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

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
vertex = [list(map(int, input().split())) for _ in range(int(input()))]


def getDistance(start, graph, distance):
    queue = deque()
    queue.append(start)
    while queue:
        x = queue.popleft()
        for i in graph[x]:
            if i == 1:
                continue
            if distance[i] == 0:
                distance[i] += distance[x] + 1
                queue.append(i)
    return distance


def solution(n, vertex):
    graph = [[] for _ in range(n + 1)]
    distance = [0] * (n + 1)

    for a, b in vertex:
        graph[a].append(b)
        graph[b].append(a)

    temp = getDistance(1, graph, distance)

    return temp.count(max(temp))


print(solution(n, vertex))

 

해설

어렵지 않게 해결할 수 있었던 그래프 문제였다.😁

각 정점 별로 거리 1로 이어지는 정점들을 저장한다.

시작 정점 1을 deque에 저장한다. while문 안에서 해당 정점을 deque에서 빼내고 그 정점으로부터 이어진 정점들까지의 거리를 계산한다. 이 때, 탐색하지 않은 정점들만 거리를 계산하는 것이 중요!! 거리 계산이 완료된 정점은 deque에 저장하고 이를 반복한다.