코딩 테스트(Python) 가장 먼 노드

문제 설명

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

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

 

 

 

from collections import deque

def solution(n, edge):
    answer = 0
    # edge의 각 항목을 오름차순으로 정렬 후 다시 정렬된 리스트로 변경
    edge = sorted([sorted(x) for x in edge])
    
    # 각 노드에 연결된 노드를 담을 그래프 생성
    graph = [[] for i in range(n+1)]
    # 각 노드의 거리 정보를 담을 배열 초기화 (0으로 시작)
    distance = [0 for i in range(n+1)]
    
    # BFS를 위한 큐 생성
    queue = deque()
    queue.append(1)  # 시작 노드는 1
    distance[1] = 1  # 시작 노드의 거리는 1로 설정
    
    # 그래프에 간선 정보 추가 (양방향 연결)
    for i, j in edge:
        graph[i].append(j)
        graph[j].append(i)
    
    # BFS 시작
    while queue:
        temp = queue.popleft()  # 큐에서 노드 하나 꺼냄
        for node in graph[temp]:
            if distance[node] == 0:  # 아직 방문하지 않은 노드라면
                queue.append(node)  # 큐에 추가
                distance[node] = distance[temp] + 1  # 현재 노드의 거리 + 1
    
    # 가장 먼 거리 구하기
    max_dis = max(distance)
    
    # 가장 먼 거리에 해당하는 노드의 개수를 셈
    for i in distance:
        if i == max_dis:
            answer += 1
    
    return answer  # 가장 먼 노드의 개수 반환