🐹 등산코스 정하기

1. 문제 링크

등산코스 정하기

2. 코드

from collections import deque

INF = int(1e9)

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

    # 연결 내용 초기화 
    for i, j, w in paths:
        graph[i].append((j, w))
        graph[j].append((i, w))
    
    intensity = [INF] * (n + 1)
    result = [0, INF]   # 산봉우리, 최소 intensity 
    q = deque([])
    for gate in gates:
        q.append((0, gate))
        intensity[gate] = 0

    while q:
        now_its, now = q.popleft()
        # 산봉우리 도착하거나 현재 확인하는 intensity가 찾은 최솟값보다 크면 더 이상 탐색 안함
        if now in summits_set or now_its > intensity[now]:
            continue 
        
        for next, next_its in graph[now]:
            if intensity[next] > max(now_its, next_its):
                intensity[next] = max(now_its, next_its)
                q.append((intensity[next], next))
    
    for summit in summits:
        if result[1] > intensity[summit]:
            result[1] = intensity[summit]
            result[0] = summit

    return result

테스트 1 〉	통과 (0.02ms, 10.3MB)
테스트 2 〉	통과 (0.02ms, 10.1MB)
테스트 3 〉	통과 (0.01ms, 10.4MB)
테스트 4 〉	통과 (0.01ms, 10.2MB)
테스트 5 〉	통과 (0.02ms, 10.4MB)
테스트 6 〉	통과 (0.06ms, 10.4MB)
테스트 7 〉	통과 (0.07ms, 10.4MB)
테스트 8 〉	통과 (0.06ms, 10.4MB)
테스트 9 〉	통과 (0.12ms, 10.4MB)
테스트 10 〉	통과 (0.27ms, 10.3MB)
테스트 11 〉	통과 (0.20ms, 10.3MB)
테스트 12 〉	통과 (0.27ms, 10.2MB)
테스트 13 〉	통과 (6.58ms, 11.8MB)
테스트 14 〉	통과 (35.10ms, 20.1MB)
테스트 15 〉	통과 (275.07ms, 74.5MB)
테스트 16 〉	통과 (291.75ms, 77.2MB)
테스트 17 〉	통과 (302.45ms, 77.1MB)
테스트 18 〉	통과 (46.09ms, 15.5MB)
테스트 19 〉	통과 (195.38ms, 33.7MB)
테스트 20 〉	통과 (479.21ms, 71.2MB)
테스트 21 〉	통과 (310.52ms, 67.4MB)
테스트 22 〉	통과 (12.84ms, 14.9MB)
테스트 23 〉	통과 (134.82ms, 31.5MB)
테스트 24 〉	통과 (75.75ms, 27.1MB)
테스트 25 〉	통과 (477.51ms, 87.6MB)

3. 해설

summit까지 도달하는 경우 중 최대 intensity가 가장 작은 값을 리턴하기 위해서 intensity배열(경로 중 최대 intensity)를 초기화해준다.

if intensity[next] > max(now_intensity, next_intensity)이면 intensity[next] = max(now_intensity, next_intensity)로 초기화해준다.

처음에는 각 출입구 별로 다익스트라 heapq를 사용하여 문제 풀이를 진행했지만 시간초과가 떴고, 모든 출입구를 heapq에 넣은 상태로 원하는 값만 찾는 방법으로 진행했다.

위 방식대로 변경한 후 모든 case를 확인해보는 것이라 굳이 우선순위 배열을 사용하여 log(n)의 추가 시간복잡도가 발생하는 heapq를 사용할 필요가 없어서 deque를 사용했다.

summit과 gate의 중복도 없애기 위해 set()을 사용했다. summit은 정렬을 해 최소 경우가 중복일 경우 작은값을 사용해주었는데, set으로 변경하는 와중 뭐가 문젠지.. 순서가 반영이 안돼서 확인하는 경우만 정렬한 list를 사용해주었다.