[프로그래머스] 가장 먼 노드 파이썬 풀이

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

프로그래머스

---

1. 풀이

• 1번 노드에서부터 각 노드까지의 최단 거리를 구해야 하므로, BFS를 활용하자

그래프를 탐색하는 방법은 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)가 있다. 이중 최단 거리를 구하는 데는 BFS를 사용한다. 사실 각 노드를 연결하는 간선의 비용을 모두 1로 둔 채 최소 비용을 구하는 다익스트라 알고리즘을 사용할 수도 있지만, 굳이 2차원 배열인 다익스트라를 사용하지 않아도 된다. 이 문제에선 리스트나 딕셔너리를 사용한 BFS만으로도 충분히 풀린다.

 

 

• 각 노드의 최단 거리를 나타내는 자료 구조를 활용하자

각 노드의 최단 거리를 나타내는 path

path라는 리스트는 1번 노드로부터 각 노드까지의 최단 거리를 저장한다. 초기 값은 INF (무한)으로 설정한다.

이후 BFS를 돌리면서 현재 노드 u와 인접한 노드 v의 최단 거리를 path[u] + 1로 초기화해 나가자.

 

 

 

2. 정답 코드

INF = 999999

def solution(n, edge):
    path = [INF] * (n + 1)
    graph = [[] for i in range(n + 1)]
    for u, v in edge:
        graph[u].append(v)
        graph[v].append(u)
        
    longest_path = find_shortest_path(graph, path)
    return path.count(longest_path)


def find_shortest_path(graph, path):
    from collections import deque
    
    queue = deque([1])
    path[1] = 0
    longest_path = -1
    
    while queue:
        u = queue.popleft()
        
        for v in graph[u]:
            if path[v] != INF: continue  # already visited node
            
            queue.append(v)
            path[v] = path[u] + 1
            longest_path = max(longest_path, path[v])
            
    return longest_path