[프로그래머스] 그래프 - 가장 먼 노드 (결과 포함)

문제 자체에 그래프, 노드, 최단 경로라는 단어들이 등장하기 때문에 최단경로 알고리즘을 사용해야겠다고 생각했다.

 

특정 시작 지점으로부터 가장 멀리있는 노드들의 개수를 구하는 것이 문제이다.

다익스트라 최단경로 알고리즘을 이용하여 시작 노드에서 다른 노드로 이동할 때 최단경로의 길이를 저장했다.

 

distance 리스트에 각 노드로 이동할 때 최단경로의 길이를 저장한다.

최초에는 굉장히 큰 수 (1e9)를 저장해놓고 인덱스에 해당하는 노드까지의 거리가 더 작으면 대체하는 식이다.

 

다익스트라 알고리즘이 끝난 후에 distance 리스트를 필터링한 이유는 가장 먼 노드의 거리를 구할 때,

최초에 비교를 위해 넣은 큰 수(1e9)가 나오지 않게 하기 위해서이다.

 

간과했던 부분은 간선이 양방향이라는 사실이었다. 간선의 정보 그대로 그래프에 넣고 다익스트라 알고리즘을 사용했는데,

5번 노드가 연결되어 있는 간선 정보는 (5, 2)로 5가 앞에 나오는 경우밖에 존재하지 않았다. 따라서 5번 노드를 건너뛰는 예외가 발생했다. 이를 해결하기 위해서 최초에 그래프 정보를 저장할 때 양방향으로 저장해주었다.

[소스 코드]

import heapq

def dijkstra(graph, distance, start):
    q = []
    
    heapq.heappush(q, (0, start))
    distance[start] = 0
    
    while q:
        d, now = heapq.heappop(q)
        
        if distance[now] < d:
            continue
        for i in graph[now]:
            cost = d + i[1]
            
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
    
    return distance
def solution(n, edge):
    INF = int(1e9)
    answer = 0
    
    graph = [[] for _ in range(n + 1)]
    distance = [INF] * (n + 1)
    
    for a, b in edge:
        graph[a].append((b, 1))
        graph[b].append((a, 1))
    
    distance = dijkstra(graph, distance, 1)
    distance = list(filter(lambda x: x != INF, distance))
    
    answer = distance.count(max(distance))
    return answer