[boj] 백준 5014 스타트링크 python 풀이

bfs로 풀 수 있는 문제로, 기존 bfs가 보통 2차원 MAP을 기준으로 하는것을 1차원으로 축소한 문제

기존 bfs의 탐색방향이 북,동,남,서 였다면 이 문제는 U,D 로 풀이

 

문제

https://www.acmicpc.net/problem/5014

5014번: 스타트링크

 

풀이

import sys
input = sys.stdin.readline
import collections

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

def bfs():
    q = collections.deque()
    q.append((S, 0))
    visited = [0 for _ in range(F)]
    visited[S-1] = 1

    while q:
        cur_stair, cnt = q.popleft()
        if cur_stair == G:
            print(cnt)
            return

        for move in [U,-D]:
            next_stair = cur_stair + move

            if 1<= next_stair<=F and visited[next_stair-1] == 0:
                visited[next_stair-1] = 1
                q.append((next_stair, cnt+1))

    print('use the stairs')