[백준/파이썬] 1753번 최단경로 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1753번 최단경로
• 문제풀이 코드 GitHub 링크
• 제출 언어: PyPy 3

풀이

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

• 자세한 문제 및 입출력 예제는 상단의 문제 출처(백준 홈페이지)를 참조해주세요

코드

import sys;read=sys.stdin.readline

v,e=map(int,read().split())
k=int(read())
d={i:[]for i in range(v)}
V=[300000]*v
V[k-1]=0
Q=set([i for i in range(v)])
for i in range(e):
    x,y,z=map(int,read().split())
    d[x-1].append([y-1,z])
    
def extractMin(Q,V):
    m=300001
    for i in Q:
        if V[i]<m:
            m=V[i]
            index=i
    return index
    
while Q:
    u=extractMin(Q,V)
    Q.remove(u)
    for l in d[u]:
        if l[0] in Q and V[l[0]]>V[u]+l[1]:V[l[0]]=V[u]+l[1]

print('\n'.join(map(lambda x:str(x)if x<300000 else'INF',V)))

설명

제 코드로는 그냥 파이썬은 통과가 안됩니다. PyPy로 제출하면 통과가 되니 참고해주세요

유명한 다익스트라 알고리즘을 사용하는 문제입니다.

다익스트라 알고리즘은 음의 가중치가 없는 그래프에서 한 노드에서 다른 모든 노드까지의 최단 거리(해당 노드까지 가는데 필요한 가중치의 최소 합)를 구하는 알고리즘입니다. 자세한 설명은 해당 나무위키 문서에 자세히 설명이 되어있습니다. 그림도 같이 있으니 참고해주세요

제가 작성한 코드와 방식은 약간 다르지만, 같은 다익스트라 알고리즘입니다.

정점의 개수가 2만개 이하이고, 가중치는 10이하이므로 대강 20만을 넘는 가중치를 주면 충분히 큰 가중치입니다. 시작단계에서 해당값으로 초기화하면 될 것입니다. E의 최대 입력값인 300,000과는 초기값이 300,000인 이유는 상관없습니다.

Q는 각 정점의 번호, id를 저장하는 집합입니다. 가장 최소의 가중치를 갖는 정점을 찾을 때 이미 계산이 끝난 노드는 제외시키기 위해 존재합니다.

V는 각 정점의 가중치를 저장하는 리스트입니다. 정점의 가중치란, 시작 노드에서 해당 노드 까지 최단 경로로 올 때, 간선의 가중치의 합에 해당합니다.

---

• 백준 문제풀이 전체 목록 보기

---