(Week7)[Dijkestra] 배달

 

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

소요시간: 30분

1. 문제 설명

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

프로그래머스

N개의 마을로 이루어진 나라의 1번 마을의 식당에서 배달이 가능한 나라의 개수를 구하는 알고리즘 

2. 접근 방식

• 다익스트라 알고리즘을 활용한다. 
• 그래프는 양방향 간선인 것을 유념해 양쪽 노드에 모두 넣어준다.
• 우선순위 큐를 사용해서, (Cost, Node) 순서로 넣어준다.
• 우선순위 큐가 빌 때까지 반복문을 진행하고, 최소거리가 갱신되면 큐에 값을 넣는다.

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. 코멘트

• 다른 스터디원과 비교했을 때, Filter를 활용하면 리스트 컴프리헨션을 활용한 것보다 좀 더 효율성을 챙길 수 있었다.
• 문제를 풀면서 양방향일 때, 왜 두 노드에 다 값을 넣어줘야 하는지에 대해 궁금했었다. 1->2, 1->3, ...으로 진행이 되다가 만약 5-> 2나 10->2이면 이를 2->5나 2->10으로 한번만 바꿔서 넣어주면 해결할 수 있을 것이라고 생각했다. 이에 대해 스터디원들과 토론을 해봤다. 여기서는 1번의 바로 옆에 2와 3 등이 올 수도 있지만, 1보다 먼저 연결된 노드가 5나 10일 수도 있는 것이다. 따라서 단방향 노드로 될 거라고 생각하면 그러한 예외처리도 해결해야하는 문제가 있을 수 있다는 결론을 내렸다.