[백준] 5014번 스타트링크 (파이썬)

문제

5014번: 스타트링크

코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
from collections import deque

def BFS(visited, S, G):
    global U, D
    queue = deque([S])
    visited[S] = 0

    while queue:
        now = queue.popleft()

        if now == G:
            return visited[now]
        
        for i in [U, -D]:
            next = now + i
            if 0 <= next < F and visited[next] == -1:
                visited[next] = visited[now] + 1
                queue.append(next)

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

visited = [-1] * F
if S == G:
    print(0)
elif (U==0 and G > S) or (D==0 and S > G):
    print('use the stairs')
else:
    BFS(visited, S-1, G-1)
    if visited[G-1] == -1:
        print('use the stairs')
    else:
        print(visited[G-1])

해설

BFS방식으로 풀었다.

S == G가 완전히 같을 경우를 넣지 않으면 틀리니 유의하자.

속도를 위해서 아예 못가는 경우를 제외하고 BFS문을 돌렸다. 최소경로를 구하라는 말에서 고민했지만, 결국에 제일 빠른길이 먼저 체크 될 것이라고 생각되어 반례를 이것저것 넣어보니 다 정답이라 출력되어 제출하였다.