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

Boo Sung Jun·2022년 3월 22일
0

알고리즘, SQL

목록 보기
51/70
post-thumbnail

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 함수를 실행하여, 시간 내에 목적지 까지 이동 가능한지 판단한다.

0개의 댓글

Powered by GraphCDN, the GraphQL CDN