[백준] 11265번 끝나지 않는 파티(python)

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

11265번: 끝나지 않는 파티

 

1. 내가 작성한 풀이

1. 노드가 500개이다, 모든 노드에서 모든 노드까지의 최단 거리를 구해줘야 한다 => 플로이드워셜 알고리즘 이용

2. 사람의 정보를 반복해주며 가능 여부를 출력해준다.

 

#플로이드 워셜 알고리즘은 노드가 500개 이하일 때 사용하는 것이 적합하다.

 

import sys
input = sys.stdin.readline

n,m = map(int, input().rstrip().split()) #n파티장 개수 m사람 수

maps = []

for i in range(n): #maps 정보 입력 받기
    maps.append(list(map(int, input().rstrip().split())))

for k in range(n): #maps를 최단거리로 변환해주기
    for i in range(n):
        for j in range(n):
            maps[i][j] = min(maps[i][k] + maps[k][j], maps[i][j])

for _ in range(m): #사람의 정보 입력받기
    a,b,c = map(int, input().rstrip().split())
    if maps[a-1][b-1] <= c: #a->b로 이동하는 최단거리가 c보다 작거나 같으면 가능
        print("Enjoy other party")
    else:
        print("Stay here")

 

+ min을 이용하면 매번 비교가 필요해 시간복잡도가 증가한다. 따라서 if문을 사용하는 것이 더 좋다.

 

위 => if문을 이용한 경우

아래 => min을 이용한 경우