[백준 🥇4] 21940번 가운데에서 만나기 (Python/파이썬)

1️⃣ 문제

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

2️⃣ 코드

친구들이 살고 있는 도시번호 때문에 헷갈렸던 문제

import sys

INF = sys.maxsize

n, m = map(int, sys.stdin.readline().split())
time = [[INF] * n for _ in range(n)]
for _ in range(m):
    a, b, t = map(int, sys.stdin.readline().split())
    time[a-1][b-1] = t

k = int(input())
city = list(map(int, sys.stdin.readline().split()))

def floyd():
    dist = [[INF] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            dist[i][j] = time[i][j]

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist


dist = floyd()
travel = []

# 왕복 거리 구하기
for i in range(len(city)):
    temp = []
    for j in range(n):
        if (city[i] - 1) == j:
            temp.append(0)
        elif dist[city[i]-1][j] == INF or dist[j][city[i]-1] == INF:
            temp.append(INF)
        else:
            temp.append(dist[city[i]-1][j] + dist[j][city[i]-1])

    travel.append(temp)

answer = []
for j in range(n):
    temp = 0
    for i in range(len(city)):
        if temp < travel[i][j]:
            temp = travel[i][j]

    answer.append(temp)

ans = min(answer)
for i in range(n):
    if answer[i] == ans:
        print(i+1, end=' ')

3️⃣ 풀이

플로이드 알고리즘으로 도시 N개 사이의 최단 시간을 구해준 뒤(NxN 리스트)
친구들이 살고 있는 도시를 출발점, N개의 도시를 도착점으로 하는 왕복 시간을 구해주었다(KxN 리스트)
그리고 N개의 도시별로 왕복시간의 최댓값을 구해주고 답을 구했다
​
여기서 내가 헷갈렸던 것은 왕복시간의 최댓값을 구해주는 부분이었는데
친구들이 살고있는 도시가 3, 2, 1이라고 하면
3번 도시에 살고있는 친구의 왕복시간은 travel 리스트의 0번 인덱스에 있음!
도시 번호를 인덱스 번호로 착각해서 인덱스 에러가 떴다

​