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

문제

가장 먼 노드 (https://programmers.co.kr/learn/courses/30/lessons/49189?language=python3)

풀이

1. 문제조건 해석

• 먼저, 현재 노드로부터 가장 멀리 떨어진 노드와의 최단거리를 찾는다.
• 이 최단거리들 중, 가장 큰 값을 가지는 거리의 개수를 찾는 문제다.

2. 알고리즘

• 전형적인 BFS 문제다. 그냥 다 탐색하면서 거리를 잰 뒤, 마지막에 거리 중 가장 큰 거 개수 세면된다.
• 진짜 그냥 주어진대로 하면 됨.

3. 코드

from collections import defaultdict, deque

def solution(n, edge):
    dists = {i:0 for i in range(1, n+1)} # 노드 1과 다른 노드들 사이의 거리를 담습니다.
    edges = defaultdict(list) # edges[node_no] 에는 node_no 노드에 연결된 노드정보를 리스트로 담습니다.
    for u, v in edge:
        edges[u].append(v)
        edges[v].append(u)

    # 노드 1부터, BFS 순회를 하며, 연결된 노드들을 순차적으로 탐색합니다.
    q = deque(edges[1])
    dist = 1
    while q:
        size = len(q)
        for i in range(size):
            v = q.popleft()

            # 만약 방문하지 않은 노드의 경우, 거리를 입력하고,
            # 그 노드와 연결된 모든 노드들을 큐에 담습니다
            if dists[v] == 0:
                dists[v] = dist
                for w in edges[v]:
                    q.append(w)
        dist += 1

    # 1로 시작하여 1로 돌아오는 거리는 필요하지않으므로 버립니다.
    del dists[1]

    # 거리 중 최대값을 구해, 이 값이 거리 배열 중 몇개나 있는지 체크합니다.
    answer = 0
    max_dist = max(dists.values())
    for i in dists.values():
        if i == max_dist:
            answer += 1
    return answer