[백준] 1753번 - 최단경로

yerimstar·2021년 12월 30일
1

그래프

목록 보기
4/4

1차시도

# 최단경로
import sys
INF = int(1e9)
V, E = map(int,sys.stdin.readline().split())
K = int(sys.stdin.readline())

# 그래프 표현
graph = [[] for _ in range(V+1)]
visited = [False] * (V+1)
weight = [INF] * (V+1)

# 가중치 입력
for _ in range(E):
    u,v,w = map(int,sys.stdin.readline().split())
    graph[u].append((v,w)) # 이웃 노드 저장

# 최단 거리 노드 찾는 함수
def get_smallest_node():
    min_value = INF
    index = 0
    for i in range(1,V+1): # 1번째 노드부터 탐색하며 최단거리 노드를 찾는다.
        if not visited[i] and weight[i] < min_value: # 아직 방문하지 않은 노드이면서 최단거리인 노드
            min_value = weight[i]
            index = i
    return index

# 다익스트라 알고리즘
def dijkstra(K):
    # 시작노드
    weight[K] = 0 # 자기자신의 가중치는 0
    visited[K] = True # 방문처리
    # 시작노드와 인접한 노드들의 최단거리 계산
    for g in graph[K]:
        weight[g[0]] = g[1]
    # 시작노드를 제외한 다른 노드들 처리 -> V-1 개
    for _ in range(V-1):
        now = get_smallest_node()
        visited[now] = True # 방문처리
        # 해당노드의 인접한 노드들의 가중치 계산
        for g in graph[now]:
            w = weight[now] + g[1]
            # 기존 가중치와 비교 후 새로 계산한 값이 더 작으면 값 업데이트
            if w < weight[g[0]]:
                weight[g[0]] = w
dijkstra(K)

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

시간초과 발생 -> heapq 사용

2차시도

# 최단경로
import sys
import heapq
INF = int(1e9)
V, E = map(int,sys.stdin.readline().split())
K = int(sys.stdin.readline())

# 그래프 표현
graph = [[] for _ in range(V+1)]
weight = [INF] * (V+1)
weight[K] = 0 # 시작노드는 자기자신이므로 가중치 값이 0이다

# 가중치 입력(입력값)
for _ in range(E):
    u,v,w = map(int,sys.stdin.readline().split())
    graph[u].append([v,w]) # 이웃 노드 저장

# heapq에 가중치 저장
heap = []
heapq.heappush(heap,[K,0]) # 시작노드의 가중치는 0

# 다익스트라 알고리즘
def dijkstra():
    while heap:
        now, now_weight  = heapq.heappop(heap) # 탐색할 노드, 가중치
        if weight[now] < now_weight: # 가중치 값 비교
            continue
        for new, new_weight in graph[now]:
            final_weight = now_weight + new_weight
            # 기존 가중치와 비교 후 새로 계산한 값이 더 작으면 값 업데이트
            if final_weight < weight[new]:
                weight[new] = final_weight
                heapq.heappush(heap,[new,final_weight])
dijkstra()
for i in range(1,V+1):
    if weight[i] == INF:
        print("INF")
    else:
        print(weight[i])

4% 시간초과........

최종

# 최단경로
import sys
import heapq
INF = int(1e9)
V, E = map(int,sys.stdin.readline().split())
K = int(sys.stdin.readline())

# 그래프 표현
graph = [[] for _ in range(V+1)]
weight = [INF] * (V+1)
weight[K] = 0 # 시작노드는 자기자신이므로 가중치 값이 0이다

# 가중치 입력(입력값)
for _ in range(E):
    u,v,w = map(int,sys.stdin.readline().split())
    graph[u].append([w,v]) # 이웃 노드 저장

# heapq에 가중치 저장
heap = []
heapq.heappush(heap,[0,K]) # 시작노드의 가중치는 0

# 다익스트라 알고리즘
def dijkstra():
    while heap:
        now_weight,now  = heapq.heappop(heap) # 탐색할 노드, 가중치
        if weight[now] < now_weight: # 가중치 값 비교
            continue
        for new_weight,new in graph[now]:
            final_weight = now_weight + new_weight
            # 기존 가중치와 비교 후 새로 계산한 값이 더 작으면 값 업데이트
            if final_weight < weight[new]:
                weight[new] = final_weight
                heapq.heappush(heap,[final_weight,new])

dijkstra()

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

도움 https://www.acmicpc.net/board/view/64342
heapq에 삽입할 때 가중치값이 우선순위가 되어야 한다.
=> heapq.heappush(heap,[가중치,노드값]) 이렇게 되어야함

profile
백엔드 개발자

0개의 댓글