5014번 파이썬

처음에 조금 많이 틀려서 문제가 없는데 뭐가 문제인지 찾아봤다.

아무래도 처음 층을 방문 처리를 안해줘서 처음 층으로 돌아왔을 때 문제가 되는 것 같다. for 문도 문제가 되는 것 같아서 if로 바꿔서 했더니 잘됐다.

 

import sys
from collections import deque
input = sys.stdin.readline

f,s,g,u,d = map(int, input().split())
def bfs(s,f):
    queue = deque([s])
    count = [0]*(f+1)
    count[s]=1
    while queue:
        floor = queue.popleft()
        if floor == g:
            print(count[g]-1)
            return
        if (floor+u)<=f and not count[floor+u]:
            count[floor+u] = count[floor] + 1
            queue.append(floor+u)
        if (floor-d)>0 and not count[floor-d]:
            count[floor-d] = count[floor] + 1
            queue.append(floor-d)
    print('use the stairs')
    return
    
bfs(s,f)

 

전에 풀었던 방식을 앞 방식을 조금 참고해서 풀었더니 이상없이 잘 풀렸다. 아무래도 처음에 했을 때 처음부터 도착층일 때 고려 안한거랑 처음 층으로 다시 돌아왔을 때의 경우를 고려하지 않아서 틀린 것 같다.

참고로 아래 방식이 시간이 거의 3분의 1정도 줄었지만 메모리 값이 늘었다! 시간을 줄일땐 아래가 효과적인 것 같다.

import sys
from collections import deque
input = sys.stdin.readline

f,s,g,u,d = map(int, input().split())
def bfs(s,f):
    queue = deque([s])
    count = [0]*(f+2)
    found=False
    count[s+1]=1
    while queue:
        floor = queue.popleft()
        if floor == g:
            found=True
            break
        for num in (u,-d):
           if 0<(floor+num)<=f and not count[floor+num+1]:
                count[floor+num+1] = count[floor+1] + 1
                queue.append(floor+num)
    if found:
        print(count[g+1]-1)
    else:
        print('use the stairs')
    
bfs(s,f)