[Baekjoon 11265] 끝나지 않는 파티

문제

💛Ⅴ [Baekjoon 11265 - 끝나지 않는 파티]

문제 풀이 방법

모든 도시에 대하여 최단거리를 구해야 하므 플로이드-워셜 알고리즘을 사용한다!

1. 최단거리를 저장하기 위한 2차원 배열을 INF로 초기화한다.
2. 자기 자신까지의 거리는 0으로 초기화한다.

3. 연결 도로에 대한 정보를 입력받는다.

   이 때, 시작과 도착도시를 연결하는 도로는 하나가 아닐 수도 있다는 조건이 있기 때문에 입력 시 최소 비용만 저장하도록 한다.

4. 모든 그래프의 순회를 n번 반복하면서 A → 현재 노드 → B로 가는 비용을 확인하고 최단 거리를 갱신한다.

풀이 코드

Python

# 플로이드 워셜 알고리즘 = 모든 지점애서 다른 모든지점까지의 최단 경로를 모두 구해야 하는 경우
import sys
input = sys.stdin.readline

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

# 플로이드 워셜 알고리즘
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])

for a,b,c in requests:
    if graph[a-1][b-1] <= c:
        print("Enjoy other party")
    else:
        print("Stay here")