[프로그래머스] 가장 먼 노드 / Python

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

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

 

 

문제풀이

단순히 시작 노드로부터의 최단경로를 구해 가장 멀리있는 공통노드들의 개수를 구하는 문제이다. 최단경로를 구하기위해 다익스트라 알고리즘을 사용하였습니다.

 

시간초과 된 코드

import heapq


def solution(n, edge):
    answer = 0
    distance = [int(1e9)] * (n + 1)
    graph = [[] for _ in range(n + 1)]

    for v in edge:
        a, b = v
        graph[a].append((b, 1))
        graph[b].append((a, 1))
    q = []
    heapq.heappush(q, (0, 1))
    distance[1] = 0
    distance[0] = 0
    while q:
        dist, now_node = q.pop()
        for g in graph[now_node]:
            next_dist = g[1]
            next_node = g[0]

            cost = next_dist + dist
            if distance[next_node] > cost:
                distance[next_node] = cost
                heapq.heappush(q, (cost, next_node))

    for d in distance:
        if d == max(distance):
            answer += 1
    return answer

 

1. edge에 저장된 두 노드에 대한 정보를 a, b로 받아줍니다.
2. 모든 간선의 길이는 똑같기 때문에 임의로 1로 설정하여 graph에 정보를 대입합니다.
3. queue에 최초 시작노드에 대한 정보를 추가합니다. 시작노드를 1로 가정할때, 자기자신인 다음노드 1까지 걸리는시간은 0입니다.
   (현재 노드에서 다음 노드까지 걸리는 시간, 현재노드) --> (0, 1)
4.  dist, now_node에 해당 정보를 대입받은 뒤 해당 노드에 연결된 다음노드를 찾기 위해 grpah[now_node]를 for문으로
   뒤져줍니다.
5. 다음노드 까지의 거리(next_dist)와 지금 노드까지의 거리(dist)를 더해 cost에 저장합니다.
6. cost가 다음 노드까지의 거리보다 작다면, 최단경로이므로 cost를 저장합니다.
7. queue에 지금까지의 dist와 다음노드에 대한 정보를 추가합니다.
8. 모든 노드에대한 최단경로를 찾을때까지 4번부터 반복

 

알고리즘상으로는 문제가 없는것같은데 마지막 테스트케이스 3개에서 시간초과 오류가 나버렸네요 하하;

 

통과된 코드

from collections import deque


def solution(n, edge):
    answer = 0
    distance = [int(1e9)] * (n + 1)
    graph = [[] for _ in range(n + 1)]

    for v in edge:
        a, b = v
        graph[a].append((b, 1))
        graph[b].append((a, 1))
    q = deque([])
    q.append([0, 1])
    distance[1] = 0
    distance[0] = 0
    while q:
        dist, now_node = q.popleft()
        for g in graph[now_node]:
            next_dist = g[1]
            next_node = g[0]

            cost = next_dist + dist
            if distance[next_node] > cost:
                distance[next_node] = cost
                q.append([cost, next_node])

    for d in distance:
        if d == max(distance):
            answer += 1
    return answer

 

같은 알고리즘이지만 데이터 추가시에 heapq가 아닌 deque를 사용하였습니다.

heapq의 경우에는 O(logN)의 시간복잡도를 가지고 deque의 경우에는 O(N)의 시간복잡도를 가집니다.