[백준] 21940번: 가운데에서 만나기

문제

백준 - 21940번: 가운데에서 만나기

분석

도시간 이동시간 정보가 주어졌을 때, 준형이와 친구들의 왕복시간들 중 최대가 최소가 되는 도시 X를 선택하는 문제이다.

도시의 개수가 최대 200개 이기 때문에, O(N^3)의 시간복잡도를 가지는 플로이드 워셜을 사용해도 된다는 판단을 했다.

문제에서 원하는 것을 살펴보자면, x라는 도시를 임의로 선택했을 때 준형이와 친구들이 x를 왕복하는 시간들이 입력받은 C에 따라 여러개가 나올 것이다. 그것들 중 최대를 구하고 x를 인덱스로 하여 최대 왕복시간을 저장해둔다. 그중 가장 작은 왕복시간이 걸리는 x들을 오름차순으로 출력하는 것이다.

따라서, 먼저 플로이드 워셜 알고리즘을 적용해서 각 도시간 최소 이동시간을 구한 뒤,
앞서 말한대로 x마다 최대 왕복시간을 구하고 그중 최소가 되는 것을 구하면 된다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
INF = sys.maxsize
time = [[INF]*(n+1) for _ in range(n+1)]
for _ in range(m):
    a, b, t = map(int, input().split())
    time[a][b] = t
k = int(input())
cities = list(map(int, input().split()))

for mid in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if time[i][j] > time[i][mid]+time[mid][j]:
                time[i][j] = time[i][mid]+time[mid][j]
result = [0]*(n+1)
for x in range(1, n+1):
    mx = 0
    for c in cities:
        if c == x or time[c][x] == INF or time[x][c] == INF: continue
        mx = max(mx, time[x][c]+time[c][x])
    result[x] = mx

ans = []
val = min(result[1:])
for i in range(1, n+1):
    if result[i] == val:
        ans.append(i)
print(*ans)

끝으로..

플로이드 워셜의 응용 문제를 풀어볼 수 있던 좋은 문제였다.