[Python] BOJ 5014 - Elevator Trouble(스타트링크)

www.acmicpc.net/problem/5014

5014번: 스타트링크

 

이런 유형의 문제를 처음 보면 '이게 왜 BFS문제지?' 라는 의문이 든다.

S층에서 G층으로 가는데 U칸 위로가거나 D칸 아래로 가야하므로

 

1. 처음에 visited[S]를 방문 처리를 해주고 q에 S를 넣는다.

 

2. q에서 pop한 뒤 x + U에 해당하는 칸에 방문한 적 있는지 확인하고 없으면 버튼을 누른 횟수를 1 증가시킨다.

 

3. 2번과 마찬가지로 x - D에 해당하는 칸에 방문한 적 있는지 확인하고 없으면 버튼을 누른 횟수를 1 증가시킨다.

 

4. 만약 x == G이면 목적지에 도착한 것이므로 (버튼 누른횟수 - 1)을 print해주고 while문을 벗어난다.

 

from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
def bfs():
	q.append(S)
	visited[S] = 1
	while q:
		x = q.popleft()
		if x == G:
			print(visited[x] - 1)
			return
		if x+U <= F and not visited[x+U]:
			visited[x+U] = visited[x] + 1
			q.append(x+U)
		if x-D > 0 and not visited[x-D]:
			visited[x-D] = visited[x] + 1
			q.append(x-D)
	print("use the stairs")
F, S, G, U, D = map(int,input().split())
q = deque()
visited = [0] * (F+1)
bfs()

(solved.ac 티어: 골드 5)

 

# 예전에 비슷한 문제인 Catch That Cow(숨바꼭질) 문제를 풀어봐서 이러한 풀이 방법이 생각났다.

   확실히 많은 유형의 문제를 풀어보니 새로운 문제를 만났을 때 예전에 풀었던 문제들의 풀이를 응용할

   수 있어서 좋다.

1697번: 숨바꼭질