[BOJ] 1719 택배

아직 노드나 에지같은 개념을 잘 몰라서 플루이드 워셜같은 개념을 이해하기 힘들었습니다. 이해가 완벽하지 않아서 엄청 해매게 되었습니다... 자료구조 개념을 공부할 필요를 느꼈습니다.

문제를 총 2가지 방법으로 풀었습니다.

첫 번째 방법은 다익스트라를 모든 적하장마다 해 주는 방법입니다.

from sys import stdin
from heapq import heappush,heappop
from math import inf
input=stdin.readline

n,m=map(int,input().split())
time_table={i:[]for i in range(n)}
route_table=[[0 for i in range(n)]for j in range(n)]

for i in range(m):
    x,y,time_spend=map(int,input().split())
    time_table[x-1].append([y-1,time_spend])
    time_table[y-1].append([x-1,time_spend])

for i in range(n):
    queue=[[0,i]]
    v_place=[inf for i in range(n)]
    v_place[i]=0
    while queue:
        s,now=heappop(queue)
        for can_go,time_spend in time_table[now]:
            if s+time_spend<v_place[can_go]:
                v_place[can_go]=s+time_spend
                route_table[can_go][i]=now
                heappush(queue,[s+time_spend,can_go])

for i in range(n):
    for j in range(n):
        print('-' if i==j else route_table[i][j]+1,end=' ' if j!=n-1 else'\n')

두 번째 방법은 플로이드-와샬의 개념을 공부한뒤 푼 방법입니다.

from sys import stdin
from collections import deque
from heapq import heappush,heappop
from math import inf
input=stdin.readline

n,m=map(int,input().split())
time_table=[[inf for i in range(n)]for j in range(n)]
route_table=[[0 for i in range(n)]for j in range(n)]

for i in range(m):
    x,y,time_spend=map(int,input().split())
    time_table[y-1][x-1]=time_table[x-1][y-1]=time_spend
    route_table[y-1][x-1]=x
    route_table[x-1][y-1]=y

for i in range(n):
    for j in range(n):
        if i==j:
            time_table[i][j]=0
            route_table[i][j]=-1

# 아마 플로이드 와샬? 워샬?
for z in range(n):
    for y in range(n):
        for x in range(n):
            if time_table[y][x]>time_table[y][z]+time_table[z][x]:
                time_table[y][x]=time_table[y][z]+time_table[z][x]
                route_table[y][x]=route_table[y][z]

for i in range(n):
    for j in range(n):
        print('-' if i==j else route_table[i][j],end=' 'if j<n-1 else'\n')

두 번째 방법으로 푼 것이 첫번째 방법으로 푼 것보다 대략 2배정도 빨랐습니다.

새로운 것들을 빠르게 알아가며 실력이 늘어난게 체감이 되었습니다..