글 읽기 - BFS말고 DP로 풀었습니다.

3juhwan 2년 전 0

BFS 분류에 있는 문제란 건 알았지만, 문제를 보자마자 BFS보단 DP로 푸는 게 간단할 거라 생각했습니다.

우선순위 큐를 이용해서 DP로 풀면 BFS보다 간단하지 않나요??

아 DP라기 보다도 메모리제이션으로 풀었습니다..

시간은 900ms 나왔습니다.

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

F, S, G, U, D = map(int, input().split())

floor = [INF] * (F + 1)
floor[S] = 0

q = []
heapq.heappush(q, (0, S))

while q:
    digit, now = heapq.heappop(q)
    upward, downward = now + U, now - D
    if upward <= F and floor[upward] > digit + 1:
        floor[upward] = digit + 1
        heapq.heappush(q, (digit + 1, upward))
    if downward > 0 and floor[downward] > digit + 1:
        floor[downward] = digit + 1
        heapq.heappush(q, (digit + 1, downward))
    
print(floor[G] if floor[G] < INF else "use the stairs")

djm03178 2년 전 2

이 코드도 결국 BFS입니다. 우선순위 큐를 사용하셨지만 거리가 항상 1씩 늘어나기 때문에 그냥 큐를 쓰는 것과 다를 게 없습니다. 메모이제이션이라고 하신 부분은 BFS 시에 거리를 기록하는 것과 같고, BFS의 방문 체크를 겸하고 있습니다. 시간 복잡도만 우선순위 큐 때문에 BFS에 비해 로그가 더 붙게 됩니다.

3juhwan 2년 전 0

답변 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

BFS말고 DP로 풀었습니다.

3juhwan 2년 전 0

djm03178 2년 전 2

3juhwan 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말