[프로그래머스] Lv.3 가장 먼 노드 (그래프) [Python, 파이썬]

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/49189
• 큐를 이용한 BFS로 구현
• 풀면서 '게임 맵 최단거리' 문제와 비슷하다고 생각이 들어서 거의 같은 방식으로 구현했다.

from collections import deque

def solution(n, edge):

    graph = {i:[] for i in range(1, n+1)} # n 개의 빈 리스트를 가진 딕셔너리 생성 (1:[], 2:[]...)

    visit = [0] * (n + 1)   # 방문 체크 및 거리 확인 리스트

    visit[1] = 1    # 시작 지점은 1로 지정

    for key, value in edge: # 양방향으로 연결된 노드들 표현하는 그래프(딕셔너리)

        graph[key].append(value)

        graph[value].append(key)

    Q = deque([(1, graph[1])]) # (출발 지점, 다음 경로 리스트)를 Q에 저장

    while Q:    # Q가 빌 때까지

        next = Q.popleft() # (출발 지점, 다음 경로 리스트)를 next에 저장, next[0] = 출발 지점, next[1] = 경로 리스트

        for node in next[1]: # 출발 지점에서 인접한 경로들에 진입

            if not visit[node]: # 방문하지 않았을 때

                visit[node] = visit[next[0]] + 1 # 현재 위치에 출발 위치로부터의 거리를 저장

                Q.append((node, graph[node]))   # 현재 위치, 현재 위치에서 인접한 경로 리스트를 Q에 저장

    return visit.count(max(visit))  # 가장 먼 거리의 개수를 리턴