문제
준형이는 내일 친구들을 만나기로 했다. 준형이와 친구들은 서로 다른 도시에 살고 있다.
도시를 연결하는 도로는 일방 통행만 있어서 도시 A{i}에서 도시 B{i}로 가는 시간과 도시 B{i}에서 도시 A{i}로 가는 시간이 다를 수 있다.
준형이와 친구들은 아래 조건을 만족하는 도시 X를 선택하여 거기서 만나려고 한다.
- 왕복시간은 자신이 살고 있는 도시에서 도시 X로 이동하는 시간과 도시 X에서 다시 자신이 살고 있는 도시로 이동하는 시간을 합한 것이다.
- 준형이와 친구들이 도로를 이용하여 갈 수 있는 도시만 선택한다.
- 준형이와 친구들의 왕복시간 들 중 최대가 최소가 되는 도시 X를 선택한다.
- 준형이와 친구들이 이동할 수 있는 도시가 최소한 하나 이상이 있음을 보장한다.
도시가 많다보니 계산하기 힘들다. 준형이와 친구들을 대신하여 도시 X를 알려주자.
위 조건을 만족하는 도시 X의 번호를 출력한다. 만약 가능한 도시 X가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다.
풀이
초기에 heapq를 이용해서 날먹을 하려다 실패했다.
문제를 잘 읽어야 하는 것이, a에서 b를 갈 수 있는데, b에서 a를 가는 길은 없을 수도 있다.
여러 시행착오를 겪다가, n이 충분히 작아서 전부 탐색을 해도 되겠다는 생각이 들었다.
우선모든 도시까지의 최단거리를 구해준 다음, 친구들 집에서 모든 도시까지의 왕복시간을 구하면서 최대값을 갱신한다.
이 논리로 친구들 도시에서 index번 도시까지의 왕복시간 중 최대값을 answer에 담고, min값을 담은 인덱스를 리턴했다.
친구들 도시에서 index번 도시를 왕복할 수 있다는 것이 이동할 수 있는 도시가 최소한 하나 이상 보장된다는 반증인 것을 이용한 풀이.
import sys
from heapq import heappush, heappop
from math import inf
si = sys.stdin.readline
def MIIS(): return map(int, si().split())
n, m = MIIS()
graph = [[inf] * (n + 1) for _ in range(n + 1)]
for a in range(1, n + 1):
for b in range(1, n + 1):
if a == b:
graph[a][b] = 0
for _ in range(m):
s, e, d = MIIS()
graph[s][e] = d
k = int(si())
friends = list(MIIS())
# j에서 k까지 가는 시간과 i를 경유해서 가는 시간을 비교해서
for i in range(1, n + 1):
for j in range(1, n + 1):
for k in range(1, n + 1):
graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])
answer = [0]
for o in range(1, n + 1):
_max = -inf
for f in friends:
# 친구집이 도착지와 같으면 0이니까 패스, 친구집에서 도착지 혹은 그 반대가 경로가 없으면 패스
if f != o and graph[f][o] != inf and graph[o][f] != inf:
# 각 친구 집에서 목적지까지의 왕복시간이 현재 최대값보다 크면 갱신
if _max < graph[f][o] + graph[o][f]:
_max = graph[f][o] + graph[o][f]
answer.append(_max)
_min = min(answer[1:])
for ans in range(1, n + 1):
if answer[ans] == _min:
print(ans, end=" ")
Smart Contract Developer