1916 최소비용 구하기

https://www.acmicpc.net/problem/1916

#다익스트라

#우선순위큐

1916번: 최소비용 구하기

#1916 최소비용 구하기
import sys

#system stdin 과 maxsize를 불러오기 위해 수입

import heapq

#heapq 우선순위큐를 사용하기 위해 수입

input=sys.stdin.readline
push=heapq.heappush
pop=heapq.heappop

#빠른 코딩과 시간을 줄이기 위해

n=int(input())

m=int(input())

#n,m입력

cost=[[] for i in range(n+1)]

#cost라기보단 입력 받는 시작 끝 비용 을 저장하기 위한 리스트, heapq을 이용하고 비용으로 우선순위를 매기기위해서 시작도시 값을 인덱스로 받고 우선순위와 도착도시를 값으로 갖는 이중리스트로 생성

 

for i in range(m):

s,a,c=map(int,input().split())

cost[s].append([a,c])

 

#짠

 

start,end=map(int,input().split())

#시작도시와 도착도시를 받아주고

 

time_table=[sys.maxsize]*(n+1)

time_table[start]=0

#현재 시작도시부터 끝도시까지 걸리는 최소비용을 나타내주는 리스트 생성 여기서 시작도시에서 시작도시로 가는 비용은 0이기때문에 0으로 설정

 

heap=[(0,start)]

#힙큐 만듭니다. 다시 말하지만 비용이 앞으로 가야합니다.

 

***********************여기서 고생했음, 비용을 앞으로 뺀다는 생각을 못하고 그냥 취향껏 도착도시 앞으로 뺐음 1번 heapq의 이해에서 다룰예정************************************************************************************************

 

while heap:

#heap을 돌립니다

 

money,now_city=pop(heap)
#heap이 가진 값을 pop하고

if money >= time_table[end]:
break

#여기서 중요** 시간을 줄이는데 가장 효율적 간단히 말하자면 a에서 b로 가는 비용이 (예를들어 start=> a, b =>end 이런 과정 사이에 드는 비용) 현재 start에서 바로 end로 가는 비용이라던지 아니면 아예 다른 c로 거쳐서 가는 비용이런걸 따졌을 때 나오는 최소비용보다 클 경우 그냥 스킵하는 겁니다.

 

#왜냐 지금 하려는건 money가 일단 최소비용보다 작다는 가정하에 그럼 now_city로 start가 가는 비용까지 다 합치면 (start = > a = > end 일때 start = > a 의 비용) 최소비용보다 작은가를 보려는 것이기 때문이다.

 

for next_city,expense in cost[now_city]:

expense1=expense+money

if time_table[next_city] > expense1:

time_table[next_city]=expense1

push(heap,(expense1,next_city))

#이제 지금 pop한 현재도시로 가는 비용을 알고있으니 이 도시를 거쳐서 end로 가는게 최소비용인지를 생각해야합니다. 아까 시작도시를 인덱스로 도착도시와 비용을 저장했으니 그 인덱스안에 있는걸 전부 풀어서 expense1로 만든 후 현재의 최소비용과 비교합니다. 그 후 다익스트라이다 이것을 거치고 가는 과정을 다시 생각하기 위해서 push 해준다

 

print(time_table[end])

#end로 가는 최소비용 출력

 

#너무 힘든 시간이였다. 예전에 푼적있었는데 데이터가 바뀌면서 실패처리 됐다길래 시간초과를 없애기위해서 바득바득 갈면서 해냈다.

중요한 점 3가지 있다.

1. heap의 이해(우선순위 큐)

 

사진까지 있으면 좀 편한데 귀찮으니깐 글로 쓰겠다.

 

우선순위 큐란 말그대로 우선순위를 비교해서 큐를 돌린다는 것이다.

 

이  문제에서 사용된 heapq는 우선순위큐를 사용하기 위함인데 heap은 거꾸로 자라는 나무라고 생각하면 된다. 간단히

 

보면 1 2 3 4 5 6 이 있다고 하자 그럼

 

    1

 2    3

4 5 6

 

이런식으로 가지를 치게 된다. 위에 있는 것이 밑에 있는것보다 작기만 하면 되는것이다.

 

이는 1 2 3 6 4 5 7 89 이렇게 있다고 했을때

 

       1

    2     3

  6  4  5  7

89

 

이렇게도 될수 있다는 뜻이다. 만약 여기서 3을 넣으면 3과 6이 바뀌게 된다. 즉 바로 위에 있는 숫자가 그 아래 숫자보다 작으면 서로 바뀐다.

 

heap은 그래서 이런 문제에서는 순서는 관계없이 최소비용을 처리해주기위해서 존재하는 것이다.

 

2. 다익스트라의 이해

 

길을 찾는다고 했을때 그 다음의 경로가 어떻게 되던간에 일단 현재의 길에서 가장 최단시간걸리는 길을 찾는것

 

예를 들어 a => b = > c와 a=>c 두개의 길이 있고 각 길은 a>b 는 2 b>c는 1 a>c는 3이 걸린다고 했을때 다익스트라는 a>b먼저 볼것이다 왜냐하면 그것이 가장 최단시간걸리는 길이기 때문

 

3. 이것을 구현하는 방법

 

굉장히 뚜렷한 문제이니만큼 개념이 없으면 힘든 것같다. 우선

 

문제를 보았을때 n=int(input()) m=int(input())부터 해주고 생각을 해본다 . 도시의 개수와 버스의 개수가 가진 의미는 도

 

시에서 도시로 버스를 이용하는데 도시는 고정되어있고 버스는 각각 다 다르게 움직인다는 것 그리고 셋째줄부터 공백

 

을 구분해시작 끝 비용으로나오고 한 버스가 끝나면 다음 버스는 줄로 구분되서 나온다는 걸 생각해서 for문으로 돌리고

 

시작 끝 비용으로 한 for문 당 다 나눠주고 마찬가지로 한 for문 당 리스트에 [시작]=[끝,비용]으로 다 담는다고 생각한다.

 

그 후 갱신될 최소비용리스트를 작성한다. 초기값은 최대값으로 설정한다. 그리고 시작도시를 기준으로 해야하기에 시작

 

도시의 최소비용은 0으로 리스트에 미리 박아놓는다. 문제에 시작도시와 끝도시는 같을 수 없다고 되어있지 않기 때문에

 

필수적으로 넣어야한다. 이를 끝내면 heap에 비용,시작값을 넣은후 풀어준다. 여기서 중요한건 비용부터 넣어야한다는

 

것 그래야 최소비용기준으로 heap이 돌아가게 된다. 작은 순서대로 비용이 처리되면서 다익스트라를 사용하게 되는 것

 

이다. 하면서 기존의 최소비용이 현재 처리중인 heap에서 pop한 도시까지 가는 비용보다 ( 즉 heap에 있는 비용 + heap

 

에 나온 도시까지 가는 비용) 클 경우 갱신한다.

 

완료 힘들다