문제 조건

input

• 노드의 개수 n
• 간선 정보를 기록한 이차원 배열 edge

output

• 1번 부터 최장 경로의 개수

문제 해석

• BFS로 완전 탐색
• 1번 노드의 각 노드의 거리를 배열에 기록

코드

def solution(n, edge):
		
		# 그래프 생성
    graph = [[] for _ in range(n + 1)]
    
    # 간선 정보를 순회하면서 그래프로 변경
    for e in edge:
        graph[e[0]].append(e[1])
        graph[e[1]].append(e[0])
    
    # 각 노드의 거리
    distances = [-1] * (n + 1)
    # 1번은 0으로 초기화
    distances[1] = 0  
    
    # 큐에 1번 노드 삽입
    queue = [1]
    
    # 큐가 빌 때 까지, 즉 모든 노드를 다 방문할 때 까지
    while queue:
        current = queue.pop(0)
        
        for neighbor in graph[current]:
		        # 아직 방문하지 않았다면 -> 방문이 가능하다면 
            if distances[neighbor] == -1: 
			          # 오기 까지의 노드 거리 + 1
                distances[neighbor] = distances[current] + 1
                queue.append(neighbor)
    
    # 가장 먼 거리를 저장할 변수
    max_distance = 0
    
     # -1을 제외하고 distances 배열에서 가장 긴 거리
    for dist in distances[1:]:
        if dist != -1:
            max_distance = max(max_distance, dist)
    
    # 해당 거리를 가지는 노드 개수 리턴
    return distances.count(max_distance)