[백준 / BOJ] 1719 택배

문제

출처 : www.acmicpc.net/problem/1719

1719번: 택배

n개의 집하장에 택배가있다.

각 집하장에서 다른 집하장으로 이동거리를 최소화하여 택배를 보낼려한다.

 

m개의 집하장 경로와 이동거리가 주어졌을때, 경로표를 만드는 문제다.

(경로표는 현재 집하장에서 다른집하장으로 택배를 이동시킬려할때 가장 먼저 거쳐가야할 집하장을 표시한 표이다.)

 

풀이

플로이드 와샬을 이용해 푸는문제다.

 

dp배열을 pair로 선언해 <최소 이동거리, 중간경로>로 저장해놓는다.

현재 i,j에 저장된 값보다 다른 경로로 가는것이 더 크다면, 업데이트를 해준다.

 

dp배열에 i에서 j로 가기위해서 거쳐가야할 최소이동거리를 가진 중간경로가 저장이 되는데, 출력해보면, (예제 1의 경우 1 -> 2 -> 5 가 아닌 1 -> 5 의 형태로) 축약돼서 저장되어있다.

앞서 저장한 dp배열의 값을 참조해서 업데이트해주기때문에, 1 -> 2 -> 5를 거쳐 가는 경로가 1 -> 5 로 저장되는것인데,

경로를 따라 올라가며 원래값으로 바꿔주면된다.

 

예를들어, 예제1의경우

 

출력 : 

- 2 3 3 2 5 

1 - 1 4 5 5 

1 1 - 4 5 6 

3 2 3 - 6 6 

2 2 3 6 - 6 

5 5 3 4 5 - 

 

답 :

- 2 3 3 2 2 

1 - 1 4 5 5 

1 1 - 4 5 6 

3 2 3 - 6 6 

2 2 3 6 - 6 

5 5 3 4 5 - 

이런식으로 출력되는데,

(1,5)를 제외한 나머지는 정상적으로 출력된다.

 

(1,5)에는 5 (5,1)에는 2가 저장되어있다.

 

1에서 5로가는 최단경로는 5로 가는것이라고 저장되어 있지만, 5에서 1로가는 최단경로는 2번을 거쳐가는것이라고 저장되어있다, 이런 지점을 찾아서 바꿔주면된다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1719%20%ED%83%9D%EB%B0%B0/main.cpp

devxb/JJUNalgo