[백준] 5014 스타트링크 Python

[백준] 5014 스타트링크 Python

이 문제가 왜 BFS,DFS 문제인지 생각해야 한다. 먼저, up과 down을 눌러가면서 진행할수록 가지가 뻗어나간다. 즉, 그래프 문제이고 탐색을 하여 최소 버튼을 누르는 횟수를 구해야하기 때문에 BFS이다.
한가지 주의해야할 점은 0 ≤ U, D ≤ 1000000 이다.
즉, up과 down 버튼이 0일 수도 있다는 것이다. 만약, up=0이게 되면 up 버튼을 누르게 되더라도 변화가 없다. 따라서, visited 배열을 선언할 때 초기값을 -1로 설정하는게 좋다.

import sys
from collections import deque
sys.stdin=open("input.txt")

f,s,g,u,d=map(int,input().split())

visited=[-1 for _ in range(f+1)]

def bfs(f,s,g,u,d):
    visited[s]=0
    q=deque()
    q.append(s)
    while q:
        x=q.popleft()

        if x==g:
            print(visited[g])
            return 0

        for i in (u,-d):
            nx=x+i
            if 0<=nx<=f and visited[nx]==-1:
                visited[nx]=visited[x]+1
                q.append(nx)
    print('use the stairs')
bfs(f,s,g,u,d)