본문 바로가기

💻 알고리즘/백준

[ 백준 ] 1719 택배 (python)

728x90

 

 

 

 

 

https://www.acmicpc.net/problem/1719

 

1719번: 택배

명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하

www.acmicpc.net

 

 

 

 

💡 접근 방법

문제에서 주어진 그래프만 보고 바로 플로이드 워셜 풀이법을 생각해냈다.

 

💖 플로이드 워셜

플로이드 워셜이란 모든 노드에서 다른 모든 노드까지의 최단 거리를 계산하는 알고리즘으로

a에서 b까지 가는 최단경로를 찾을 때, min(a -> b까지의 거리, a -> k + k -> b까지의 거리) 값을 구해 최단경로로 설정해주면 된다.

 

즉, 수식으로 나타내면 아래와 같다.

 

다익스트라 알고리즘처럼 단계별로 거쳐가는 노드를 기준으로 최단거리를 계산하지만 차이점이 있다.

다익스트라 알고리즘은 매 단계별 방문하지 않은 노드를 찾아서 최단 경로를 검색하고,

플로이드 워셜 알고리즘은 매 단계마다 모든 노드를 계산해준다.

 

* 플로이드 워셜에 대한 설명은 이 유튜브에 자세히 설명되어 있으므로, 개념을 모른다면 꼭 참고하는것을 추천한다.

 

 

 

다시 문제로 돌아가서 이 문제는 플로이드 워셜 알고리즘과 약간 다른점이 존재했다. 플로이드 워셜 알고리즘은 최단 경로를 기록하는 대신, 이 문제에선 최단 경로일 때 가장 먼저 방문하는 노드의 번호를 기록해야 한다는 점이 달랐다.

 

그래서 처음 경로를 입력 받을 때, 경로를 담는 graph와 지나는 지점을 기록하는 res 배열 두 개를 만들어서 구현을 해주었다. 근데 여기서 실수를 했던게 나는 graph[a][b] > graph[a][k] + graph[k][b] 인 경우에만 res[a][b]를 방문점으로 변경해주면 된다라고 생각했다.

하지만 아무곳을 거치지 않고 바로 도착하는 경우라면, 도착점이 가장 먼저 방문하는 노드이므로 res[a][b] = b 로 기록을 해줘야 했다.

 

즉, 예를 들어 아래 그림과 같이 노드 1 -> 노드 2로 이동하는 최단 경로는 다른 점을 거치지 않고 바로 노드1에서 노드2로 가는 방법뿐이다. 이럴 때 res[1][2]의 값은 2(거리값이 아닌 2번 노드라는 의미)가 된다는 뜻이다.

 

 

이 부분만 유의해서 플로이드 워셜 알고리즘 방법대로 구현해주면 문제를 쉽게 풀어갈 수 있다.

 

 

 

 

 

 

🔥 문제 풀이

 

1️⃣ graph를 입력받을 때, res도 함께 입력 받아 준다. -> 처음 입력 받을 땐 위에서 설명한 대로 도착점을 res에 넣어준다.

2️⃣ 플로이드 워셜 알고리즘 기본 코드를 작성해, 만약 graph[a][b] > graph[a][k] + graph[k][b] 가 된다면 graph[a][b]의 값을 graph[a][k] + graph[k][b]로 변경해주고, res[a][b]의 값을 res[a][k]로 변경해준다. (가장 처음 방문하는 점을 기록해야 하기 때문이다)

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
import heapq
import sys
input = sys.stdin.readline
 
INF = int(1e9)
 
n, m = map(int, input().split())
 
graph = [[INF] * (n + 1for _ in range(n + 1)]
res = [[INF] * (n + 1for _ in range(n + 1)]
 
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = c
    graph[b][a] = c
 
    res[a][b] = b
    res[b][a] = a
 
for i in range(1, n + 1):
    graph[i][i] = 0
    res[i][i] = INF
 
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            if graph[a][b] > graph[a][k] + graph[k][b]:
                graph[a][b] = graph[a][k] + graph[k][b]
                res[a][b] = res[a][k]
 
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if res[i][j] == INF:
            res[i][j] = '-'
 
for i in res[1:]:
    print(*i[1:])
cs

 

 

 

 

 

728x90