1 minute read

가장 먼 노드

문제 링크

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

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한 사항

  • 노드의 개수 n은 2 이상 20,000 이하입니다.
  • 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
  • vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

그림1

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

그림2

문제 풀이

  1. 양방향 노드 정보를 저장한 이후 BFS 방식으로 각 노드의 최단 탐색 거리들을 저장한다.
  2. 노드들의 거리 정보를 저장한 배열에서 최대값이 총 몇 개가 되는지 출력한다.
from collections import defaultdict, deque

def solution(n, edge):
    answer = 0
    nodes = defaultdict(list)
    distances = [0] * (n+1)
    
    for a, b in edge : 
        nodes[a].append(b)
        nodes[b].append(a)

    deq = deque([])
    for n in nodes[1] : 
        deq.append([n, 1])
        distances[n] = 1
        
    while deq :
        if min(distances[2:]) != 0 :  # 2 이상인 노드의 최단 거리들이 모두 초기값이 아닐때 (모든 노드들을 방문했을 때) 나가기
            break
        now, d = deq.popleft()

        for next in nodes[now] :
            if next != 1 and distances[next] == 0 :
                distances[next] = d+1
                deq.append([next, d+1])

    answer = distances.count(max(distances))  # 최대값이 총 몇 개인지 출력
    return answer

Comments

You May Also Enjoy