등산코스정하기-python(kakao22 season)

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

프로그래머스

다익스트라를 입맛대로 바꾼문제

 

그러므로 왕복을 구하는게 아닌 일단 목적지까지 제일 intensity가 낮은 값을 찾는 방법을 찾는다면 그방법고대로 다시 돌아오면 된다.

출발지를 어디서 시작하건 summit을 어디가던 그냥 제일 intensity가 짧은 상태를 유지하는 곳에서 시작하고 도착하면 된다는 문제해결방법이였다.

원래는 최단거리를 구하기 위해 가중치의 합을 비교하는게 다익스트라인데 여기서는 intensity가 가장 낮은값을 찾아서 가야하기에 최댓값 비교로 살짝 커스텀해야겠다고 생각을 함.

heapq를 이용하지 않으면 매번 최단시간소요 찾아야하고 현재노드와 연결된걸 일일이 찾아야 하기에 시간복잡도가 올라가기에 올라감

우선순위큐로 다익스트라를 하면 O(ElogV) V는 노드의 개수 E는 간선의 개수

 

1. 처음 출발지들을 힙에 넣어준다. 그런데 여기서 시간은 0으로 

2. 현재까지의 비용이 젤 작은것을 빼서 그 노드까지 가는 타임테이블보다 그 노드까지의 비용이 비싸면 그냥 continue

3. 만약 현재보는 노드가 summits안에 있다면 answerlist에 넣어주고  continue 

4. 그것두 아니라면 현재 노드에 연결되어 있는 노드들과 시간들을 하나씩 nextnode 위치에 더 낮은 intensity로 갈수 있다면 그 다음노드인덱스의 타임테이블을 갱신하고 힙에 넣어준다.

5. 계속 돌면서 어차피 타임테이블에는 최소값만들어있을테고 정상찍어도 continue기에 큐가 다 빠지면 반복문 종료하고 answer출력되는데 여기서 sort안해줬다가 틀렷어 ㅠㅠ 

뒤에꺼를 기준으로 만약 같다면 앞에껏도 오름차순으로 정렬을 해주고 해당하는 각각을 출력해준다.

import heapq
def solution(n, paths, gates, summits):
    graph = [[] for _ in range(n+1)]
    for a, b, time in paths:
        graph[a].append((b,time))
        graph[b].append((a,time))
    INF = int(1e9)
    timedistance = [INF for i in range(n+1)]
    pq = []
    for start in gates:
        timedistance[start] = 0
        heapq.heappush(pq, (0,start))
    answer = [] 
    while pq :
        dist, a = heapq.heappop(pq)
        if timedistance[a] < dist:
            continue
        if a in summits:
            answer.append([a,timedistance[a]])
            continue
        for nxt, td in graph[a]:
            td = max(timedistance[a],td)
            if timedistance[nxt] > td:
                timedistance[nxt] = td
                heapq.heappush(pq,(timedistance[nxt],nxt))
    answer.sort(key=lambda x: (x[1],x[0]))
    return answer[0][0],answer[0][1]