(Week7)[Dijkestra] 가장 먼 노드

 

주간 코딩스터디 때 푼 문제들을 정리하고 있습니다. 구체적인 문제에 대한 정보는 게시글 내 링크를 살펴봐주세요

소요시간: 30분

1. 문제 설명

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

프로그래머스

n개의 노드가 있는 그래프에서 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지 return

2. 접근 방식

• 다익스트라 알고리즘을 활용해 문제를 푼다. 
• heapq를 활용해서 우선순위큐를 만든다(해당 문제에서는 우선순위가 크게 중요하지 않아보임(거리가 모두 1임))
• '양방향 노드'라는 것을 기억해야 한다. 5번 노드에서 2번 노드로 가는 입력이 있으면, 2번 노드에서 5번 노드로 가는 입력도 넣어줘야 한다.

3. 코드

import heapq
def solution(N, road, K):
    INF = 1e9
    graph = [[]for _ in range(N+1)]
    distance = [INF] * (N+1)
    for road_n in road:
        a, b, c = road_n
        graph[a].append((b, c))
        graph[b].append((a, c))
    q = []
    distance[1] = 0
    heapq.heappush(q, (0, 1))
    while q:
        dist_a, node_a = heapq.heappop(q)
        # 이미 처리된 노드의 경우
        if distance[node_a] < dist_a:
            continue
        for node_b, dist_b in graph[node_a]:
            new_dist = dist_a + dist_b
            if new_dist < distance[node_b]:
                distance[node_b] = new_dist
                heapq.heappush(q, (new_dist, node_b)) # cost를 키값으로 정렬이 된다. 
    return len(list(filter(lambda x: x <= K, distance)))

4. 코멘트

• 다익스트라 알고리즘을 활용해서 쉽게 문제를 풀었지만, 스터디에서 시간복잡도를 봤을 때 (파이썬 분들과 비교해도) 가장 낮았었다. 내 생각에는 해당 문제에서는 크게 필요없는 부차적인 부분이 들어갔기 떄문이라고 생각한다.(예를 들어 INF 거리를  -1로 변경하는 부분 등)
• 그래도 변수명이 직관적이어서 이해가 쉬웠다는 좋은 피드백을 받을 수 있었다.
• INF 대신 파이썬에서는 float('inf')를 활용해 Infnit 변수를 만들 수 있다고 한다. 이걸 활용하면 굳이 변수를 정의하지 않고, 코드를 좀 더 직관적으로 짤 수 있을 것 같다.