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

문제

https://www.acmicpc.net/problem/21940
백준 문제집 - 0x1C강 - 플로이드 알고리즘

 

알고리즘: 그래프 이론, 최단 경로, 플로이드-워셜

---

풀이

 

플로이드 워셜을 이용해 왕복시간을 계산하는 문제다.

문제 설명에 "최대가 최소"라고 되어있는데, 약간 불친절한 설명인듯...

준형이와 친구들은 모두 다른 마을에 살고있다.
따라서 어떤 마을 A에 대한 왕복시간은 모두 다르다.
만약 A 마을의 왕복시간이 [100, 10, 90, 110] 일경우, A 마을에 대한 왕복시간은 110이 된다. (최대)
위 과정을 반복해서 1 ~ N 마을의 최대 왕복시간 리스트가 [110, 90, 200, 100, 90]이 되었을때, X가 될 수 있는 마을은 2번, 5번 마을이다. (최소)

 

참고로 처음 풀이할때는 딕셔너리를 사용해서 모든 마을의 왕복시간들을 저장했었고, 다시 풀이할때는 리스트를 사용했는데 실행시간이 꽤 차이난다.

전체 코드

# 메모리: 33432KB / 시간: 924ms
from sys import stdin


input = stdin.readline
INF = int(1e9)

def main():
    def floyd_warshall(graph: list) -> list:
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
        return graph


    def calc() -> list[int]:
        """ X가 될 수 있는 마을 후보들 구하기 """
        min_time = INF  # 최소 왕복시간
        towns = []  # X가 될 수 있는 마을들

        # 최대가 최소 = X까지 가는 왕복시간 중 최댓값이, 다른 마을로 가는 왕복시간들 중 최솟값인경우.
        for X in range(N):
            time = 0  # 현재 마을 기준 최대 왕복시간
            for curr in C:
                curr_time = graph[curr][X] + graph[X][curr]
                if curr_time == INF:
                    break
                time = max(time, curr_time)

            # 만약 다른 마을 왕복시간보다 작다면, 최솟값과 town 리스트 갱신.
            # 같다면 town 리스트에 현재 마을 추가
            if time < min_time:
                towns = [X]
                min_time = time
            elif time == min_time:
                towns.append(X)
        return towns


    N, M = map(int, input().split())
    graph = [[INF] * N for _ in range(N)]

    for i in range(N):
        graph[i][i] = 0

    for _ in range(M):
        A, B, T = map(int, input().split())
        graph[A-1][B-1] = T

    K = int(input())
    C = list(map(lambda x: int(x)-1, input().split()))

    graph = floyd_warshall(graph)
    towns = calc()

    print(" ".join(map(lambda x: str(x+1), towns)))


main()