[Python] 가장 먼 노드

문제 참고

프로그래머스

 

 

코드 작성

실패 # 1

def solution(n, edge):
    answer = 0
    INF = int(1e9)
    graph = [[INF] * (n + 1) for _ in range(n + 1)]
    
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            if a == b:
                graph[a][b] = 0
    
    for e in edge:
        graph[e[0]][e[1]] = 1
        graph[e[1]][e[0]] = 1
        
    for k in range(1, n + 1):
        for a in range(1, n + 1):
            for b in range(1, n + 1):
                graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
                
    max_value = max(graph[1][1:])
    for g in graph[1]:
        if g == max_value:
            answer += 1
    return answer

플로이드 워셜 알고리즘을 이용했더니 시간초과가 터져버렸다..

O(n^3)의 시간복잡도를 가져서 안되나 보다..

 

성공 #1

from heapq import heappush, heappop

def solution(n, edge):
    answer = 0
    INF = int(1e9)
    graph = [[] for _ in range(n + 1)]
    distance = [INF] * (n + 1)
    
    for e in edge:
        graph[e[0]].append((1, e[1]))
        graph[e[1]].append((1, e[0]))
    
    def dijkstra(start):
        heap = []
        heappush(heap, (0, start))
        distance[start] = 0
        while heap:
            dist, now = heappop(heap)
            if distance[now] < dist:
                continue
            for g in graph[now]:
                cost = dist + g[0]
                if cost < distance[g[1]]:
                    distance[g[1]] = cost
                    heappush(heap, (cost, g[1]))
    dijkstra(1)
    max_dist = max(distance[1:])
    for d in distance:
        if d == max_dist:
            answer += 1
    
    return answer

힙구조를 이용한 다익스트라 알고리즘은 O(ElogV)의 시간복잡도를 가지고 있어서 그런지 시간이 터지지 않았다.

(E: 간선의 개수, V: 노드의 개수)

 

기본 다익스트라 알고리즘 코드를 이용하였으므로 따로 설명하지는 않겠다.