[BFS] 프로그래머스 Lv3. 가장 먼 노드 - python

🗂️ 문제

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

프로그래머스

 

💡 접근법

모든 노드의 가중치가 동일했기 때문에 BFS를 사용하여 최단 거리를 구했다.

1번 노드에서 모든 노드까지의 최단 거리를 구하고, 그 중 가장 긴 거리를 구한 뒤, 거리 배열에서 가징 긴 거리의 개수를 구했다.

 

😎 내 코드

from collections import deque

def BFS(v, graph, visited):
    distances = [0 for _ in range(len(visited))]
    
    visited[v] = True
    queue = deque([v])
    
    while queue:
        node = queue.popleft()
        for new_node in graph[node]:
            if not visited[new_node]:
                visited[new_node] = True
                distances[new_node] = distances[node] + 1
                queue.append(new_node)
    
    return distances

def solution(n, edge):
    answer = 0
    
    graph = [[] for _ in range(n+1)]
    for a, b in edge:
        graph[a].append(b)
        graph[b].append(a)
    
    visited = [False for _ in range(n+1)]
    dists = BFS(1, graph, visited)
    
    return dists.count(max(dists))