[Python] 프로그래머스 / Level3 / 가장 먼 노드 (최단거리 알고리즘)

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

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

최단거리 알고리즘

문제를 읽고, 최단거리 알고리즘을 이용해 풀이 해야한다는 것은 판단할 수 있었다. 

다음은 대표적인 최단거리 알고리즘 2개이다.

• 다익스트라 알고리즘 (Dijkstra) 
• 플로이드 워셜 알고리즘 (Floyd-Warshall)

 

😨 잘못된 풀이 : 플로이드 워셜

처음엔 아무생각 없이, 다익스트라보다 플로이드 워셜 알고리즘이 더 사용하기 편했기 때문에 플로이드 워셜 알고리즘으로 문제를 풀었다.

def solution(n, edges):
    answer = 0; INF = 99999
    graph = [ [] for _ in range(n+1) ]
    
    for edge in edges:
        node1, node2 = edge[0], edge[1]
        graph[node1].append(node2)
        graph[node2].append(node1)
    
    distance = [ [INF] * (n+1) for _ in range(n+1) ]
    
    for i in range(n+1): distance[i][i] = 0
    
    for i in range(n+1):
        nodes = graph[i]
        for node in nodes:
            distance[i][node] = 1
        
    for k in range(1,n+1):
        for a in range(1,n+1):
            for b in range(1,n+1):
                distance[a][b] = min(distance[a][b], distance[a][k]+distance[k][b])

    return distance[1][1::].count(max(distance[1][1::]))

 

😨 그 결과 

정확도 테스트는 통과했지만, 효율성 테스트를 통과하지 못했다.

그때 든 생각 : 앗, 이런 내가 문제 조건을 제대로 안 봤구나.

 

다시 제한사항에게 관심을 주었다. 역시 ,, N 조건이 10^4 (1만) 을 넘어갔다. 

플로이드 워셜 알고리즘의 시간 복잡도는 O(N^3) time 이기 때문에 효율성 테스트를 통과 못하는 것은 당연하다.

(보통 10^9 이상의 연산 횟수를 가지면 효율성 테스트를 통과하지 못한다)

 

O(N^2)의 복잡도를 가지는 다익스트라 알고리즘을 사용했어야 한다.

 

😊 올바른 풀이 : 다익스트라

import heapq
def solution(n, edges):
    answer = 0; INF = 99999
    graph = [ [] for _ in range(n+1) ]
    distance = [INF] * (n+1)
    distance[1] = 0
    
    for edge in edges:
        node1, node2 = edge[0], edge[1]
        graph[node1].append(node2)
        graph[node2].append(node1)
        
    # dijkstra
    q = []
    heapq.heappush(q,(0,1))
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist : continue
        
        for v in graph[now]:
            cost = dist + 1
            if cost < distance[v] : 
                distance[v] = cost
                heapq.heappush(q,(cost,v))
            
    return distance.count(max(distance[1:]))

 

 

😊 결과

정확성 + 효율성 통과 성공