[BOJ] 1753번 최단경로 / 사용언어 : 파이썬(python)

※ 문제링크

1753번: 최단경로

※ 참고사이트

[백준] 1753번(python 파이썬)

해당문제는 다익스트라 알고리즘을 활용하여 풀 수 있는 문제였다. 문제해결을 위해 알고리즘에 대한 이해가 선행되어야 한다고 생각하여 구글링을 통해 다익스트라 알고리즘에 대한 이해를 하고 자체적으로 해결해보려는 시도를 했다. 처음에는 그래프를 2차원 배열로 구현하고, 방문기록과 가중치리스트를 다차원배열로 구현하여 해당 알고리즘을 구현해보앗는데, 배열의 크기로 인해 메모리 초과가 나왔다. 다양한 방법으로 코드를 수정해보았지만 해결되지 않아 구글링을 통해 다른 사람들의 풀이방법을 보면서 다익스트라 알고리즘을 효과적으로 구현하는 방법을 숙달하는 방식으로 진행하였다.

자세한 풀이방법과 코드는 아래와 같다.

1. 입력값을 바탕으로 그래프와 가중치 값을 기록할 리스트를 작성한다.

2. 최소힙을 이용하여 최단거리를 탐색할 수 있는 함수를 구현한다.

3. 최단거리를 탐색후 결과 값을 출력한다.

+ 해당 문제는 sys함수를 사용하지 않으면 통과가 불가능하다. 개행문자에 유의하여 사용해주도록 하자

 

# 실패사례
from collections import deque
import sys
import heapq
from copy import deepcopy

input = sys.stdin.readline
V, E = map(int, input().split()) # V: 정점의 개수 / E: 간선의 개수
start = int(input())
graph = dict() # 딕셔너리로 그래프 구현
distance = [[[float('inf'), k, i] for i in range(V+1)] for k in range(V+1)]
visited = [[False for _ in range(V+1)] for _ in range(V+1)]
for _ in range(E):
    u, v, w = map(int, input().split()) # u: 출발점 / v: 도착점 / w: 가중치
    if distance[u][v][0] > w: # 간선이 여러개일때 가장 작은 가중치를 가진 값으로 가중치 갱신
        distance[u][v][0] = w
    if u not in graph:
        graph[u] = [v]
    else:
        graph[u].append(v)

# 자기자신의 가중치를 0으로 적용 / 자기자신의 위치를 방문한 것으로 변경
for i in range(V+1):
    distance[i][i][0] = 0
    visited[i][i] = True

# 간선이 없는 정점들에 빈 리스트로 값 할당 
for i in range(1, V+1):
    if i not in graph:
        graph[i] = []

def dijkstra(start):
    queue = deque()
    check = deepcopy(distance[start])
    check.pop(start) # 자기자신 삭제
    check.pop(0) # 패딩부분 삭제
    heapq.heapify(check) # 계산시 사용할 리스트 힙으로 변환
    for _ in range(len(check)):
        cps = heapq.heappop(check)[2]
        visited[start][cps] = True
        queue.extend(graph[cps])
        while queue:
            cpe = queue.popleft()
            # 거리 비교후 최단 거리로 해당 거리 갱신
            if distance[cps][cpe][0] + distance[start][cps][0] < distance[start][cpe][0] and visited[start][cpe] == False:
                visited[start][cpe] = True
                distance[start][cpe][0] = distance[cps][cpe][0] + distance[start][cps][0]
dijkstra(start)

for i in range(1, V+1):
    if i == V:
        sys.stdout.write(f'{distance[start][i][0]}')
    else:
        sys.stdout.write(f'{distance[start][i][0]}\n')
        
# https://pacific-ocean.tistory.com/281 참조
import sys
from heapq import heappush, heappop
inf = 100000000 
v, e = map(int, input().split())
k = int(input())
s = [[] for _ in range(v + 1)]
dp = [inf] * (v + 1)
heap = []
def dijkstra(start):
    dp[start] = 0
    heappush(heap, [0, start])
    while heap:
        w, n = heappop(heap)
        for n_n, wei in s[n]:
            n_w = wei + w
            if n_w < dp[n_n]:
                dp[n_n] = n_w
                heappush(heap, [n_w, n_n])
for i in range(e):
    u, v, w = map(int, input().split())
    s[u].append([v, w])
dijkstra(k)
for i in range(1, len(dp)):
    if dp[i] == inf:
        dp[i] = 'INF'
for i in range(1, len(dp)):
    if i == len(dp)-1:
        sys.stdout.write(f'{dp[i]}')
    else:
        sys.stdout.write(f'{dp[i]}\n')

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.