📙 가장 먼 노드

프로그래머스

from collections import deque

def bfs(graph, start):
    distance = {node: float('inf') for node in graph}
    distance[start] = 0
    queue = deque([start])
    
    while queue:
        current_node = queue.popleft()
        for neighbor_node in graph[current_node]:
            if distance[neighbor_node] == float('inf'):
                distance[neighbor_node] = distance[current_node] + 1
                queue.append(neighbor_node)
    
    return distance

def solution(n, edge):
    answer = 0
    
    graph = {i: [] for i in range(1, n+1)}
    for u, v in edge:
        graph[u].append(v)
        graph[v].append(u)
    
    distances = sorted(list(bfs(graph, 1).values()))
    longer_nodes = distances.count(distances[-1])
    
    return longer_nodes

왜 이렇게 풀었을까?

• 우선 그래프 탐색은 초기화 과정이 기본입니다.
• 그래프를 초기화(저는 딕셔너리를 이용하여 초기화하였지만 리스트를 사용해도 무방합니다) 후 각 노드의 연결 정보까지도 graph에 추가해줍니다.
• 노드 간의 최단 경로를 탐색하기 위해 bfs 함수를 설계하였고, 이 함수에서는 거리 정보를 먼저 초기화합니다.
• 시작 지점에서 시작 지점까지는 거리가 당연히 0이고, bfs는 dfs와 다르게 큐를 사용하기 때문에 파이썬에서는 이를 deque으로 쉽게 구현할 수 있습니다.
• 시작 노드부터 인접한 노드를 하나씩 거쳐가며 거리를 계산하고, 큐에 인접 노드를 추가하고 빼는 방식의 결과로 그래프의 모든 노드를 탐색하게끔 진행할 수 있습니다.
• 마지막으로 거리 정보를 반환하여 그 중 최댓값을 가지는 노드들이 몇 개인지 파악하여 결과를 출력하도록 구현해보았습니다.
• bfs로 그래프를 탐색하는 기본적인 문제라고 생각하고, 이를 심화하여 다양한 문제가 나올 수 있으니 지속적으로 관련 문제(MST 등)를 풀어봐야겠습니다.