[백준] 11265 끝나지 않는 파티

문제

• N개의 파티장이 있다. 
• 파티장 사이에는 일방통행 도로가 있고, 각 도로별로 이동하는데 걸리는 시간이 다르다.
• M명의 손님이 현재 위치한 A파티장에서 C시간 이후 파티가 열리는 B파티장까지 시간내에 도착할 수 있는지 확인하기
• 도착 가능하면 "Enjoy other party", 시간 내에 도착 못하면 "Stay here" 출력하기

 

• 5 <= N <= 500
  1 <= M <= 10,000
  1 <= C <= 1,000,000,000

 

풀이 1

• 플로드 워셜로 최단거리를 모두 구한 뒤, 손님 별로 a->b 파티장의 최단 거리가 c 보다 큰지 판단하기

 

시간초과

import sys
input = sys.stdin.readline

N, M = map(int, input().split())    # 파티장 크기, 손님 수
graph = [list(map(int, input().split())) for _ in range(N)]

# 최단거리 구하기 ; 플로드 워셜 
for k in range(N) :
    for a in range(N) :
        for b in range(N) :
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 손님 별 요청 처리
for _ in range(M) :
    a, b, c = map(int, input().split())

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

 

풀이 2

• `min` 사용시 비교 후 매 번 graph[a][b]에 값을 할당하는 작업을 수행한다.
  -> 조건문을 사용하면 값이 변경되어야 할 때만 할당하는 작업이 수행된다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())    # 파티장 크기, 손님 수
graph = [list(map(int, input().split())) for _ in range(N)]

# 최단거리 구하기 ; 플로드 워셜 
for k in range(N) :
    for a in range(N) :
        for b in range(N) :
        	if graph[a][b] > graph[a][k] + graph[k][b] :
            	graph[a][b] = graph[a][k] + graph[k][b]

# 손님 별 요청 처리
for _ in range(M) :
    a, b, c = map(int, input().split())

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

 

References

• 백준 최단거리