[프로그래머스 Lv.3] 가장 먼 노드

프로그래머스

from collections import deque

def solution(n, edge):
    answer = 0
    
    graph = [[] for _ in range(n+1)]
    visited = [False]*(n+1)
    route = []
    
    for start,end in edge:
        graph[start].append(end)
        graph[end].append(start)
    
    def bfs(index):
        
        visited[index] = True
        
        queue = deque([(index,0)])
        
        route.append((index,0))
        
        while queue:
            v, depth = queue.popleft()
        
            for node in graph[v]:
                if not visited[node]:
                    visited[node] = True
                    queue.append((node,depth+1))
                    route.append((node,depth+1))
        
    bfs(1)
    
    max_distance = max([x[1] for x in route])
    
    route = [x for x in route if x[1] == max_distance]
    
    return len(route)

이번 문제는 주어진 간선 정보들로 이루어진 그래프에서 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하는 문제이다.

 

먼저 그래프로 표현하기 위해 2차원 리스트(graph)를 선언하고, 양방향으로 저장해주었다.

 

그 후 BFS를 사용하여 route 라는 리스트에 '이동한 경로'와 '이동한 거리'를 저장해주었고, 최종적으로 가장 긴 거리(max_distance)를 구하여 해당 거리를 움직인 노드들의 개수를 반환해주었다.

 

인접 리스트로 표현한 그래프와 BFS를 사용하여 푼 간단한 문제였다 :)