[Python] 스타트 링크 5014 - bfs 그래프 탐색

1. 문제 

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

5014번: 스타트링크

 

 

2. 문제 요약

• S > G로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 찾는 문제 → 탐색 문제

 

 

3. 아이디어 정리

BFS로 그래프 탐색을 진행하여 최솟값을 찾아본다.

1. S를 큐에 넣어 탐색을 시작한다.
2. 위로 올라가는 경우: 방문을 안 했다면 큐에 넣고, 버튼 누른 수 저장
3. 아래로 내려가는 경우: 방문을 안 했다면 큐에 넣고, 버튼 누른 수 저장

 

 

4. 문제 풀이

4-1. 내 풀이

import sys
from collections import deque
"""
   S > G로 가기 위한 버튼의 수의 최솟값 - bfs 
"""
# 고층, 현재, 도착할 곳, 위, 아래
F, S, G, U, D = map(int, sys.stdin.readline().split())

visit = [-1] * (F + 1)  # 방문 유무 체크용 & 방문 횟수용 
dq = deque()
dq.append(S)
visit[S] = 0  # 방문 횟수 넣기

while dq:
    now = dq.popleft()
    # 1. 위로 올라가는 경우, 범위에 맞고 방문을 안 한경우: 결과 넣고 큐에 넣고 버튼 누를 수 저장 
    if now + U <= F and visit[now + U] == -1:
        visit[now + U] = visit[now] + 1
        dq.append(now + U)
    # 2. 아래로 내려가는 경우, 범위에 맞고 방문을 안 한경우: 결과 넣고 큐에 넣고 버튼 누를 수 저장
    if now - D >= 1 and visit[now - D] == -1:
        visit[now - D] = visit[now] + 1
        dq.append(now - D)

if visit[G] == -1:
    print("use the stairs")
else:
    print(visit[G])

 

 

5. 결론

bfs문제로 이전에 풀어본 숨바꼭질 문제와 비슷하다. 비슷한 문제를 풀고 싶으면 아래 문제 링크를 풀어보자!

• 숨바꼭질

1697번: 숨바꼭질