[백준 1238번] 파티

난이도: 골드 3

문제 링크: www.acmicpc.net/problem/1238

1238번: 파티

백준 1238번 파티

최단 경로 문제를 공부한 후 연습 삼아 풀어본 문제입니다 (블로그 글 링크).

 

1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000으로, 입력되는 데이터의 양이 아주 많은 편은 아닙니다.

하지만 문제를 자세히 보면, 최단 경로를 총 N번 찾아야 합니다.

c번 도시를 제외한 다른 도시들로부터 c번 도시로 갈 때 총 N-1번, c번 도시에서 다른 도시로 갈 때 1번.

따라서 플로이드-워셜 알고리즘으로 풀 수 있습니다. 단, 플로이드-워셜 알고리즘은 O(N^3)의 시간복잡도를 가지므로, 데이터 N ≤ 1000일 때 사용할 수 있으며, 사용하는 언어에 따라 시간 제한에 걸릴 수 있습니다. Python이라면 시간 제한에 걸릴 것이고, C++라면 아슬아슬하게 시간제한 이내에 들어올 수 있을 것입니다.

또, 다익스트라 알고리즘으로 접근해 볼 수 있습니다. 간단한 다익스트라 알고리즘은 O(N^2)의 시간 복잡도를 가지므로, N번 알고리즘을 돌리면 총 O(N^3)의 시간 복잡도를 가져, 큰 도움이 되지 않을 것입니다. 따라서 개선된 다익스트라 알고리즘을 이용하여 O(NM log N)의 시간 복잡도를 가지도록 풀 수 있습니다.

 

1. 다익스트라 알고리즘 버전

목적지 도시 c가 있을 때, c로부터 모든 도시로 가는 코스트 + 모든 도시로부터 c로 가는 코스트가 최대가 되는 경우를 찾으면 되는 문제입니다.

따라서 기본적인 다익스트라 알고리즘을 그대로 사용하면 됩니다.

저는 우선 c도시에서 모든 다른 도시로 가는 값을 최단거리 배열에 저장해 두고, 각 도시에서 c도시로 가는 비용을 구한 후, 이를 앞에서 구한 값과 더한 다음, 이를 cur_max 라는 값과 비교하여 더 큰 값일 경우 갱신하는 방법으로 접근하였습니다.

 

2. 플로이드-워셜 알고리즘 버전

문제의 성격 상, 오히려 이쪽이 문제를 풀기에는 더 알맞은 알고리즘입니다.

2차원 최단거리 배열을 구한 후, d[i][c] + d[c][i] 중 최대가 되는 값을 찾으면 됩니다.

그 외 나머지 아이디어는 다익스트라 알고리즘 때와 비슷합니다.

 

 

실제로 풀었을 때 채점 결과입니다.

실행 결과; 아래가 다익스트라, 위가 플로이드-워셜 입니다.

실행 시간에서 큰 차이가 나는 것을 알 수 있습니다.

시간 제한이 1초였으니, 플로이드-워셜 접근법의 경우 간신히 시간제한 범위를 만족하였습니다.