알고리즘/문제 풀이

[Python/파이썬 백준 5104] 스타트링크(BFS)

광규니 2021. 3. 4. 15:02
반응형

www.acmicpc.net/problem/5014

 

5014번: 스타트링크

첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.

www.acmicpc.net

풀이

일차원 BFS 문제입니다.

S,G 를 start, end값으로 선언했으며

U,D 을 dx 값에 +U 와 , -D 를 넣어줬습니다

check 값을 비교해서 queue에 삽입되면 +1씩 시켜줬으며 check[end]를 반환시켜줘서

출력시켰어용~~

# 스타트링크

# 일차원 BFS 문제이며, U,D 을 nx 값에 넣어줘서
# check 해당 값 출력
from collections import deque
import sys
input=sys.stdin.readline

F,S,G,U,D = map(int,input().split())
dx =[U,-D]
graph=[[] for _ in range(F)]
check=[-1 for _ in range(F)]


def bfs(start,end):
    queue=deque()
    queue.append(start)
    check[start]=0
    while queue:
        x=queue.popleft()
        for i in range(2):
            nx= x +dx[i]
            if 0<=nx<len(graph) and check[nx]==-1:
                queue.append(nx)
                check[nx]=check[x]+1
    return check[end]
cnt=bfs(S-1,G-1)

if cnt==-1:
    print("use the stairs")
else:
    print(cnt)
반응형