[프로그래머스] 등산코스 정하기

문제 링크:

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

회고:

• 다익스트라 알고리즘 활용 (참고 링크)
• 힙(heap)을 사용하면 가중치가 가장 작은, 방문하지 않은 다음 노드를 쉽게 구할 수 있다.
• python 원소 in list vs 원소 in set 비교
  • 원소 in list
    • 파이썬 리스트는 요소들이 연속적인 메모리 공간에 순차적으로 저장되는 배열 기반의 자료구조이다.
    • 특정 요소의 존재 여부를 확인하려면 리스트의 처음부터 끝까지 요소를 하나씩 확인해야 한다. (선형 검색)
    • 따라서 리스트 길이가 n인 경우 in 연산의 시간 복잡도는 O(n)
  • 원소 in set
    • 파이썬 집합은 해시 테이블을 기반으로 구현된 자료구조이다.
    • 집합에 요소를 추가하거나, 특정 요소가 집합에 있는지 확인하는 연산은 해시 함수를 사용하여 요소의 해시값을 계산하고, 그 해시값에 해당하는 위치에 요소가 저장되어 있는지 확인한다.
    • 최상의 경우 해시 충돌이 없으면 한 번의 연산으로 요소 확인 가능하여 in 연산의 평균적인 시간 복잡도는 O(1) 이다.
    • 최악의 경우 모든 요소를 검사할 수 있으므로 O(n)일 수도 있으나, 일반적으로는 O(1) 으로 생각하면 될 듯.
• 즉, 특정 요소가 포함되어 있는지 확인하는 로직이 필요하다면 list 보다는 set이 효율적
  
  

python

from heapq import heappop, heappush


INF = 1e9


def solution(n, paths, gates, summits):
    graph = [[] for _ in range(n + 1)]
    summits_set = set(summits)

    for i, j, w in paths:
        graph[i].append([j, w])
        graph[j].append([i, w])

    heap_queue = []  # (intensity, node)
    distance = [INF] * (n + 1)

    # 모든 출발지를 우선순위 큐에 삽입
    for gate in gates:
        heappush(heap_queue, (0, gate))
        distance[gate] = 0

    while heap_queue:
        intensity, node = heappop(heap_queue)

        # 산봉우리이거나 intensity가 더 크다면 이동하지 않음
        if node in summits_set or distance[node] < intensity:
            continue

        #  해당 노드에서 이동할 수 있는 곳으로 이동
        for next_node, weight in graph[node]:
            new_intensity = max(intensity, weight)
            if distance[next_node] > new_intensity:
                distance[next_node] = new_intensity
                heappush(heap_queue, (new_intensity, next_node))

    min_node = 0
    min_intensity = INF
    summits.sort()

    for summit in summits:
        if distance[summit] < min_intensity:
            min_node = summit
            min_intensity = distance[summit]

    return [min_node, min_intensity]


if __name__ == "__main__":
    result = solution(
        n=7,
        paths=[[1, 2, 5], [1, 4, 1], [2, 3, 1], [2, 6, 7], [4, 5, 1], [5, 6, 1], [6, 7, 1]]	,
        gates=[3, 7],
        summits=[1, 5]
    )

    print(result)

[5, 1]