1753_최단경로

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

1753번: 최단경로

 

 

처음에 문제를 접하고 나서 든 생각은 graph를 하나두고 시작점을 기준으로 한 배열을 하나두고 그 배열을 채워나가면 될 것 같았다.

 

이때 시작점을 기준으로 한배열의 경우

0번째 index는 시작점 --- 0 번 노드 사이의 간격

1번째 idnex는 시작점 --- 1 번 노드 사이의 간격

 

식으로 채울 생각이었다.

 

import sys
from collections import deque
input = sys.stdin.readline

v,e = map(int,input().split())
k = int(input())
INF = int(1e9)
visited = [ INF for _ in range(v+1)  ]
graph = [[] for i in range(v+1)]

for _ in range(e):
    u,v,w = map(int,input().split())
    graph[u].append((v,w))

q = deque([[k,0]])

while q:
    node,cnt = q.popleft()
    for i,j in graph[node]:
        visited[i] = min(visited[i],cnt + j)
        q.append((i,visited[i]))

print(0)
for i in range(2,v+2):
    print(visited[i] if visited[i] !=INF else 'INF')

bfs를 활용해서 deque를 구현해서 풀었는데 메모리초과가 났다... 고민하다가 결국 인터넷을 조금 참조하였는데 que구조가 아닌 최소 힙 구조를 이용해서 풀어야 메모리가 초과가 나지 않았다.

 

 

 

 

 

import sys
import heapq
input = sys.stdin.readline

V,e = map(int,input().split())

k = int(input())
INF = int(1e9)
distance = [INF] * (V+1)

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


for _ in range(e):
    u,v,w = map(int,input().split())
    graph[u].append((v,w))

q = []
heapq.heappush(q,(0,k))
distance[k] = 0

while q:
    cnt,node = heapq.heappop(q)
    if distance[node] < cnt:
        continue
    for i,j in graph[node]:
        if cnt+j < distance[i]:
            distance[i] = cnt + j
            heapq.heappush(q,(cnt+j,i))


for i in range(1, V+1):
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])

 

코드는 사실 거의 유사하다. 왜 que구조가 아닌 heap 구조로 해야할까??

 

 

 

++++

import sys
from collections import deque
input = sys.stdin.readline

v,e = map(int,input().split())
k = int(input())
INF = int(1e9)
visited = [ INF for _ in range(v+1)  ]
graph = [[] for i in range(v+1)]

for _ in range(e):
    u,v,w = map(int,input().split())
    graph[u].append((v,w))

q = deque([[k,0]])

while q:
    node,cnt = q.popleft()
    for i,j in graph[node]:
        if visited[i] > cnt + j:
            visited[i] = cnt + j
            q.append((i,visited[i]))

print(0)
for i in range(2,v+2):
    print(visited[i] if visited[i] !=INF else 'INF')

 

뭔가 이 코드로도 동작시켜보고 싶어서 다음과같이 했더니 시간초과가 났다.

 

결국 heap 구조와 큐 구조의 차이인것 같다. heap은 최소의 값이 가장 위로 올라가게 된다. 즉, 가중치가 가장 작은 것부터 검사를 하게되고 if문을 통해서 가중치가 큰것은 바로바로 쳐내기 때문에 통과가 되는 것이다.

 

https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

위 글을 읽고오면 조금더 이해가 편할 것이다.