[프로그래머스] 가장 먼 노드 | 파이썬 (💡 최단 경로 알고리즘)

문제 설명

프로그래머스

 

문제 풀이

가장 멀리 떨어지 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드를 의미한다는 부분에서 다익스트라 최단 경로 알고리즘을 사용해야겠다고 생각했다.

 

전체 코드

import heapq

def dijkstra(start):
    q = []
    
    # 시작 노드로 가는 최단경로는 0
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

def solution(n, edge):
    INF = int(1e9)
    
    global distance, graph
	
    distance = [INF] * (n + 1)		# 최단경로
    graph = [[] for i in range(n + 1)]	# 간선의 정보
    
    for i in range(len(edge)):
        a, b = edge[i]
        graph[a].append((b, 1))
        graph[b].append((a, 1))
    
    start = 1
    dijkstra(start)
    
    # 최단경로가 가장 긴 노드의 개수 구하기
    max_val = max(distance[1:])
    answer = distance.count(max_val)
    return answer

 

다익스트라 알고리즘을 사용해 시작 노드에서부터 다른 노드로 가는 각각의 최단경로를 구한 후, 최단경로 테이블에서 경로가 가장 긴 노드의 개수를 구해 출력했다.

 

다익스트라 알고리즘에 대한 자세한 설명과 코드는 여기 참고❗

 

---

그래프 문제가 이전보다 덜 무섭다,,, 이코테👍👍👍

 

코딩테스트 연습 - 가장 먼 노드