[Python] BOJ(백준) 1238번 - 파티

링크

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

난이도(solved.ac 참고)

골드3

풀이

다익스트라 이론을 접하고 백준에서 기본 문제들(1753 최단경로, 1916 최소비용구하기, 18352 특정거리의도시찾기)을 풀었는데, 이론만 알면 그냥 풀 수 있는 문제였어서 재미가 없었다. 그래서 더 난이도가 높은 문제들 중 제출 횟수가 많은 이 문제를 선택했다.

 

다익스트라 함수의 기본 틀은 거의 같다. 다익스트라 함수를 어떻게 활용하는지가 중요한 문제였다고 생각한다. 물론 이 문제도 다익스트라의 기본 개념만 알면 어렵진 않다.

 

N개의 숫자로 구분된 각각의 마을에 한 명씩 살고 있다고 했다. 그러므로 1부터 n의 범위를 갖는 for문을 돌면서 다익스트라 함수를 실행한다. 여기서 중요한 부분은, 거리 배열을 매 반복문 실행 시마다 초기화를 시켜줘야 된다는 것이다. 그렇게 하지 않으면 최초 실행으로 인해 바뀐 distance를 기준으로 다시 한 번 함수를 실행하게 되기 때문에 정확한 distance를 측정할 수 없다. 함수를 실행했을 때 인덱스 x에 해당하는 값이 바로 각자의 집에서 파티를 벌이는 x번 마을까지의 최단 경로가 될 것이다. 이 다익스트라 함수를 실행한 값을 result라는 2차원 배열에 넣었다. 

 

그리고 1차원 배열인 time_list를 선언해서 배열의 [i][x]의 값 + [x][i]의 값을 넣었다. 이 뜻은, 각자의 집에서 파티를 벌이는 마을인 x까지의 최단 경로 + 파티를 벌이는 마을 x에서 각자의 집 i까지의 최단 경로 에 해당한다.

 

예제 입력을 기준으로 위 코드를 실행했을 때 n번만큼 다익스트라 함수를 실행한 결과값을 넣은 result 배열을 예시로 들어 설명하겠다.

[
[],
[1000000000, 0, 4, 2, 6],
[1000000000, 1, 0, 3, 7],
[1000000000, 2, 6, 0, 4],
[1000000000, 4, 3, 6, 0]
]

이 result는 각 위치에서 다른 위치까지의 최단 경로를 나타낸 2차원 배열이다. 여기에서 첫번째 배열의 4가 뜻하는 것은, 1번 마을에서 파티를 여는 x번(여기서는 2번) 마을까지의 최단 경로이고, 두번째 배열의 1은 파티를 여는 x번(여기서는 2번) 마을에서 1번 마을까지의 최단 경로이다. 즉 1번 마을에 사는 학생이 파티에 참여하기 위해 x번 마을까지 갔다 온 최단 경로의 길이가 4 + 1 = 5 라는 것이다.

 

마찬가지로 3, 4번 학생에 대해서도 진행을 하면 각각 6+3, 3+7의 값이 나오는 것을 확인할 수 있다. (2번 학생은 움직일 필요가 없으므로 제외)

 

결국 time_list라는 배열에 들어가는 값은, [5, (0), 9, 10]이 되는 것이고 우리는 여기에서 가장 큰 값인 10을 출력하면 되는 것이다.

 

처음에는 다익스트라를 각자의 위치에서 x번 마을까지 한 번, 그리고 x번 마을에서 각자의 위치까지 한 번 이렇게 두 번 해야될 줄 알았는데, 생각해보니까 예제 입출력 표의 x번째 행의 값이 결국 x번 마을을 기준으로 한 다익스트라의 결과값이었다. 그러므로 각자의 위치에서(파티를 여는 x번 마을에 사는 경우도 전부 포함하여) 다익스트라 함수를 실행하면 따로 x번 마을에서 다시 다익스트라 함수를 실행할 필요가 없다.