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

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

문제링크

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

11265번: 끝나지 않는 파티

 

⚾ 코드

# 11265 끝나지 않는 파티
import sys
input = sys.stdin.readline
N, M = map(int, input().split())  # N: 파티장의 크기, M: 서비스를 요청한 손님의 수


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

# 입력 받을 때 for문을 통해 list.append로 입력을 받는 것 보다
# 리스트 내포(List  Comprehension)를 통해 입력 받는 것이 더 빠름.
# graph = []
# for _ in range(N):
#     graph.append(list(map(int, input().split())))

for k in range(N):
    for i in range(N):
        for j in range(N):
            
            # 최솟값을 갱신할 때 min을 쓰면 작든, 크든 모든 경우에 갱신하므로
            # if 문을 사용했을 때보다 시간이 오래 걸린다.
            
            if graph[i][k]+graph[k][j] < graph[i][j]:
                graph[i][j] = graph[i][k]+graph[k][j]

            # graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])

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")

 

🔔 해결 과정 & 깨달은 점

- 알고리즘 : 플로이드 워셜 알고리즘

- 처음에 무작정다익스트라 알고리즘 방식으로 풀다가 플로이드 워셜 알고리즘으로 풀어야 한다고 깨닫고 코드를 수정했다. 문제를 끝까지 잘 읽고 접근하자고 다짐했다.

- 코드를 다 맞게 작성한 것 같은데 계속 시간초과 에러가 났다. 분명히 내가 적은 코드 어딘가에서 시간 초과가 발생하고 있는 것이라 판단되어서 하나씩 수정해봤다.

1. min 으로 최솟값을 갱신한 부분을 if 문을 써서 해봤다.

최솟값을 갱신할 때 min을 쓰면 비교 후 모든 경우에 대해서 갱신을 하지만, if 문은 조건에 맞을 때만 갱신을 하기 때문에 속도가 빨라졌다. 따라서 python과 pypy3모두 통과되지 않았지만 이렇게 코드를 바꿔보니 pypy3에서는 통과하였다.

2. 입력을 받을 때 list.append가 아닌 List Comprehension으로 입력을 받았다.

List Comprehension이 list.append보다 속도가 더 빠르다고 한다.

이렇게 바꾸니 python에서도 통과가 되었다.

- min을 쓸 때는 불필요하게 업데이트 되는 값이 없을 때 사용하도록 하자.

- 그리고 List Comprehension이 가능한 상황에서는 되도록 List Comperhension을 사용하도록 하자.