[Programmers]Python_가장 먼 노드

문제

문제 설명

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

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

제한사항

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

코드

from collections import defaultdict, deque
def solution(n, vertex):
    nodes = defaultdict(list) #양방향이기때문에 각 노드별 연결된 노드들을 저장
    
    for x, y in vertex:
        nodes[x].append(y)
        #1로 시작하니 1로 가는 것은 볼 필요없음
        if y != 1:
            nodes[y].append(x)
            
    #노드별 레벨 저장
    check = [-1] * (n + 1)
    #bfs
    q = deque([(1, 0)])
    
    while q:
        #현재 레벨과 노드 pop()
        node, level = q.popleft()
        #현재 레벨의 노드 저장
        check[node] = level
        
        for nxt_node in nodes[node]:
            if check[nxt_node] == -1: #연결되지 않은 노드이므로 0으로 바꿈으로서 연결됨으로 표시
                check[nxt_node] = 0
                q.append((nxt_node, level + 1)) #다음 노드를 다음 레벨로 저장
    return check.count(max(check)) #가장 높은 레벨의 노드 개수 return

 

진행 과정

예제 #1

n = 6

vertex = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

 

1) node = 1, level = 0

2) answer = [-1, 0, -1, -1, -1, -1, -1]

3) q = [(3, 1)]

4) q = [(3, 1), (2, 1)]

 

5) node = 3, level = 1

6) answer = [-1, 0, 0, 1, -1, -1, -1]

7) q = [(2, 1), (6, 2)]

8) q = [(2, 1), (6, 2), (4, 2)]

 

9) node = 2, level = 1

10) answer = [-1, 0, 1, 1, 0, -1, 0]

11) q = [(6, 2), (4, 2), (5, 2)]

 

12) node = 6, level = 2

13) answer = [-1, 0, 1, 1, 0, 0, 2]

 

14) node = 4, level = 2

15) answer = [-1, 0, 1, 1, 2, 0, 2]

 

16) node = 5, level = 2

17) answer = [-1, 0, 1, 1, 2, 2, 2]

 

18) return 3 #가장 높은 레벨 2의 개수