[BFS] 백준 5014번 : 스타트링크 - 파이썬 Python

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

5014번: 스타트링크

 

생각하기 

버튼을 누르는 최소 횟수를 구하는 것이기 때문에 전형적인 BFS 문제라고 생각하였다

 

시간 복잡도

S, G, F가 모두 1000000 이하의 수이므로 충분히 BFS로 풀어도 시간 안에 들어올 수 있는 문제

 

구현하기

q = deque()

• (현재 강호가 있는 층, 현재까지 누른 버튼의 횟수) 를 q에 append / popleft 한다

 

올라가는 버튼

• 현재 강호가 있는 층 + U 가 건물을 넘지 않아야 함
• visited에 있는 층이 아니어야 함

 

내려가는 버튼 

• 현재 강호가 있는 층 - D가 건물을 넘지 않아야 함
• visited에 있는 층이 아니어야 함

 

from collections import deque

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

q = deque()
visited = set()
visited.add(S)
q.append((S, 0))

while q:
    cur, cnt = q.popleft()
    if cur == G:
        print(cnt)
        exit(0)
    
    if (1<= cur + U <= F) and (cur+U not in visited):
        visited.add(cur+U)
        q.append((cur+U, cnt+1))

    if (1<= cur - D <= F) and (cur-D not in visited):
        visited.add(cur-D)
        q.append((cur-D, cnt+1))

print('use the stairs')