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

풀이

from collections import deque
def solution(n, edge):
    answer = 0
    # 연결된 노드 정보 그래프
    graph = [[] for _ in range(n+1)] 
    # 각 노드의 최단거리 리스트
    distance = [-1] * (n+1)
    
    # 연결된 노드 정보 추가
    # graph = [[], [3, 2], [3, 1, 4, 5], [6, 4, 2, 1], [3, 2], [2], [3]]
    for e in edge:
        graph[e[0]].append(e[1])
        graph[e[1]].append(e[0])

    ### BFS
    # BFS를 위한 큐, 출발 노드는 1
    queue = deque([1])
    # 출발 노드의 최단거리는 0
    distance[1] = 0
    # BFS 수행
    while queue:
        now = queue.popleft()
        # 현재 노드에서 이동할 수 있는 모든 노드 확인
        for i in graph[now]:
            # 아직 방문하지 않은 노드라면
            if distance[i] == -1:
                queue.append(i)
                # 최단거리 갱신
                distance[i] = distance[now] + 1
    # 가장 멀리 떨어진 노드 개수 구하기
    for d in distance:
        if d == max(distance):
            print(max(distance))
            answer += 1
    return answer

1️⃣ 연결된 노드 정보 그래프(graph)와 각 노드의 최단거리를 저장하는 리스트(distance) 생성
2️⃣ grpah에 노드 연결 정보를 추가하는 데, 간선이 양방향이므로 양쪽으로 추가해줘야 함
3️⃣ BFS를 위한 큐(queue)를 생성하고, 출발 노드는 1, 출발 노드의 최단거리는 0
4️⃣ BFS 수행

• 현재 노드(now)를 가져온다.
• 현재 노드에서 이동할 수 있는 모든 노드를 확인한다. 아직 방문하지 않은 노드라면 queue에 추가하고 최단거리를 갱신

5️⃣ 가장 멀리 떨어진 노드 개수를 구한다.