[Python] 백준 11265 - 끝나지 않는 파티 문제 풀이

Overview

BOJ 11265번 끝나지 않는 파티 Python 문제 풀이
분류: Shortest Path (최단거리), Dijkstra(다익스트라), Floyd-Warshall(플로이드와샬)

---

문제 페이지

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

---

풀이 코드 1 - 플로이드 와샬

from sys import stdin
from typing import List


def floyd_warshall(n: int, graph: List[List[int]]) -> None:
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if graph[i][k] + graph[k][j] < graph[i][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]


def main():
    def input():
        return stdin.readline().rstrip()

    n, m = map(int, input().split())
    graph = [[0] * (n + 1)] + \
            [[0] + list(map(int, input().split())) for _ in range(n)]

    floyd_warshall(n, graph)

    for _ in range(m):
        a, b, c = map(int, input().split())
        if graph[a][b] <= c:
            print("Enjoy other party")
        else:
            print("Stay here")


if __name__ == "__main__":
    main()

플로이드와샬 알고리즘을 이용하여 각 파티장으로 이동하는데 걸리는 최단 시간을 구한다.

---

풀이 코드 2 - 다익스트라

from sys import stdin
from typing import List
from heapq import heappop, heappush


n: int
m: int
graph: List[List[int]]


def dijkstra(start: int, dest: int, time: int) -> bool:
    if graph[start][dest] <= time:
        return True

    hq = []
    for i in range(1, n + 1):
        if i != start:
            heappush(hq, (graph[start][i], i))

    while hq:
        dist, node = heappop(hq)
        if dist > time:
            return False

        if dist > graph[start][node]:
            continue

        for neighbor in range(1, n + 1):
            if neighbor == node:
                continue
            if dist + graph[node][neighbor] < graph[start][neighbor]:
                graph[start][neighbor] = dist + graph[node][neighbor]
                heappush(hq, (graph[start][neighbor], neighbor))
            if neighbor == dest and graph[start][neighbor] <= time:
                return True

    return False


def main():
    def input():
        return stdin.readline().rstrip()
    global n, m, graph

    n, m = map(int, input().split())
    graph = [[0] * (n + 1)] + \
            [[0] + list(map(int, input().split())) for _ in range(n)]

    for _ in range(m):
        a, b, c = map(int, input().split())
        if dijkstra(a, b, c):
            print("Enjoy other party")
        else:
            print("Stay here")


if __name__ == "__main__":
    main()

다익스트라를 이용한 풀이이다. 채점 결과 pypy3는 통과하지만 python3는 시간초과가 발생한다.
손님이 파티장으로 이동할 때마다 dijkstra 함수를 실행하여, 시간 내에 목적지 까지 이동 가능한지 판단한다.