[백준/파이썬]1753번 - 최단경로 / 다익스트라

---

접근 방법

 

하나의 점에서 각 정점까지의 최단경로를 모두 구해야하기 때문에 다익스트라 알고리즘을 사용하였다.

처음에는 모든 점까지의 거리를 최대로 설정해놓고, 하나씩 방문해가며 거리를 좁혀갔다.

---

풀이

 

간선의 정보를 길이 v의 리스트를 만들어 각각의 u, v, w에 대해 아래와 같이 저장하였다.

line = [[] for j in range(n)]
for i in range(m):
  u, v, w = map(int, input().split())
  line[u - 1].append((v - 1, w))

 

각 정점을 방문 할때마다 가장 가까운 점을 알아내야 하므로 이부분을 따로 함수로 만들었다.

 

---

정답 코드

import sys

input = sys.stdin.readline
INF = 100000000
n, m = map(int, input().split())
k = int(input()) - 1
line = [[] for j in range(n)]
for i in range(m):
  p1, p2, t = map(int, input().split())
  line[p1 - 1].append((p2 - 1, t))

visited = [0] * n
dis = [INF] * n

def min_dis():
  min = INF
  min_index = 0
  for i in range(n):
    if visited[i] == 0 and dis[i] < min:
      min = dis[i]
      min_index = i
  return min_index

def d(k):
  visited[k] = 1
  for i in line[k]:
    if dis[i[0]] > i[1]:
      dis[i[0]] = i[1]

  for i in range(n - 1):
    x = min_dis()
    visited[x] = 1
    for j in line[x]:
      if dis[j[0]] > dis[x] + j[1]:
        dis[j[0]] = dis[x] + j[1]

d(k)

for i in range(n):
  if i == k:
    print(0)
  elif dis[i] == INF:
    print("INF")
  else:
    print(dis[i])

---

오답 풀이

 

1.

처음에는 간선의 정보를 이차원 배열에 가중치만 저장했었는데 메모리 초과가 나왔다.

처음에 line 리스트의 크기가 n+1가 아닌 n인 이유도 처음의 메모리 초과를 피하기 위한 변경이였다.

결국 지금과 같이 바꾸어 메모리 초과를 피할 수 있었다.

2.

한 정점에서 같은 정점으로 가중치가 2개 이상 존재하는 경우 앞의 가중치를 덮어버리는 문제가 있었다.

중간에 선택된 정점의 경우 크기 비교를 매번 하기때문에 상관이 없지만

시작 정점인 k에서는 문제가 되었다.

그래서 처음 dis에 단순히 대입시키는게 아닌 크기비교를 진행하도록 하였다.