[ Programmers 49189 ] 가장 먼 노드(Python)

문제

https://programmers.co.kr/learn/courses/30/lessons/49189

1번 노드에서 가장 먼 노드를 찾는 bfs 문제다.

문제 풀이

1. 주어진 행렬을 양방향 그래프로 만들어준다.
2. 연결된 노드로 이동하면서 queue에 (현재 위치, 이동 거리)를 저장해줄 것이다.
3. 방문 안한 노드로 이동할 때 (이동한 위치, 이동거리 + 1)를 queue에 넣어준다.
4. 가장 큰 이동 거리를 answer 변수에 저장하고, 노드는 answer_list에 저장해주면 된다.

코드

from collections import defaultdict
from collections import deque


def solution(n, edge):
    graph = defaultdict(list)
    for node in edge:
        graph[node[0]].append(node[1])
        graph[node[1]].append(node[0])

    q = deque()
    q.append([1, 0])

    dist = [-1 for _ in range(n+1)]
    dist[1] = 0

    answer = 0
    answer_list = []

    while q:
        print(q)
        v, w = q.popleft()
        for u in graph[v]:
            if dist[u] == -1:
                q.append([u, w+1])
            dist[u] = max(dist[u], w+1)
            
            if dist[u] > answer:
                answer = dist[u]
                answer_list = [v]
            elif dist[u] == answer:
                answer_list.append(v)

    answer_list = list(set(answer_list))
    return len(answer_list)