99클럽 코테 스터디 3일차 TIL - 문제에 맞는 알고리즘을 떠올리기

문제 1 - 배달 문제링크

오늘 배운 점

문제의 장식을 치워버리고 어떤 알고리즘을 적용할 수 있는지 생각하자.

여러 가지의 풀이 방법이 떠오를 땐 가장 쉽게 구현할 수 있는 것을 택하자.

문제를 꼼꼼히 읽어보자.

 

사고 과정

1번 마을에서 다른 마을까지 K시간 내에 배달할 수 있는 마을들을 구하는 문제다.

마을과 통행시간으로 해당 문제를 장식해 놓은 것을 확인했다. 따라서 장식을 제거하여 그래프상의 노드와 간선 가중치로 치환한다.

즉, 1번 노드로부터 최소 거리가 K 이하인 모든 노드들을 구하면 된다. 

이에 맞는 알고리즘은 다익스트라 알고리즘이다.

다익스트라 알고리즘을 알고 있었다면 바로 눈에 보이는 문제였다.

"""
    다익스트라 문제
    특정 점에서 다른 모든 지점까지의 최단거리를 구하면 된다.
"""
import heapq
def solution(N, road, K):
    answer = 0

    graph = [[] for _ in range(N + 1)]

    for r in road:
        u, v, w = r
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    dist = [float('inf') for _ in range(N + 1)]
    dist[1] = 0

    hq = []
    heapq.heappush(hq, (0, 1))

    while hq:
        cur = heapq.heappop(hq)

        if cur[0] != dist[cur[1]]:
            continue

        for nxt in graph[cur[1]]:
            if cur[0] + nxt[1] < dist[nxt[0]]:
                dist[nxt[0]] = cur[0] + nxt[1]
                heapq.heappush(hq, (dist[nxt[0]], nxt[0]))

    for val in dist:
        if val <= K:
            answer += 1
             
    return answer

 

문제를 풀다가 제동이 걸렸던 점들

1. u, v, w = r 로 u, v, w에 할당하는 방식은 시간적으로 손해인가? 라는 의문.

2. deque으로 구현하다가 다익스트라는 최단거리부터 뽑아서 계산해야 한다는 사실을 기억하고 최소힙으로 변경함.

3. while문 끝나고 dist 순회시 범위를 도시1은 포함 안되도록 인덱스를 2부터 진행했고 틀렸다. 확인해보니 도시1도 포함이어서 1로 변경했다.