백준 5014번 : 스타트링크 in Python

5014번: 스타트링크

 

www.acmicpc.net

이 문제는 F층으로 이루어진 고층 건물에서 위로 U층을 가는 버튼과 아래로 D층을 가는 버튼만을 가지는 엘리베이터를 타고 S층에서 G층으로 가려고 할 때 눌러야 하는 버튼의 최소 횟수를 구하는 문제이다. 이때 U와 D의 값에 따라 도달할 수 없는 층이 존재할 수 있는데, 그때는 'use the stairs'를 출력한다.

이를 해결하기 위해서는 S층을 시작으로 하는 BFS를 시행해야 한다. 즉, S층을 시작으로(즉, S를 queue에 넣은 뒤 while loop에서 S를 꺼낸다.) 위로 U층 가는 경우와 아래로 D층 가는 경우를 고려해 만약 도착한 곳이 1층 이상 F층 이하이고, 아직 방문하지 않은 곳이라면 해당 층을 방문했다고 표시하고, 그 층을 방문할 때까지 누른 버튼의 횟수를 저장한다. 그리고 해당 층을 queue에 저장해 후에 이 층에서 버튼을 누른 경우를 고려한다. 이를 queue가 빌 때까지 반복하면 BFS 시행을 완료하게 된다.

BFS를 시행 중에 만약 queue에서 꺼낸 수가 목적 층인 G와 같다면 지금까지 버튼을 누른 횟수를 출력하고 바로 BFS를 종료한다. BFS를 끝낸 뒤에 만약 출력을 한 적이 없다면 이는 G층에 절대 도달할 수 없음을 의미하므로 'use the stairs'를 출력한다.

이를 코드로 구현하면 다음과 같다.

from collections import deque
import sys
input = sys.stdin.readline
F, S, G, U, D = map(int, input().split())
queue = deque()
queue.append(S)
# 각 층에 도달하기 위해 버튼을 누른 횟수의 최솟값를 저장하는 배열
building = [0 for _ in range(F+1)]
# 각 층을 방문했었는지를 나타내는 배열
visited = [False for _ in range(F+1)]
# 초기값 설정
visited[S] = True
arrived = False
# BFS를 실행한다.
while queue:
    u = queue.popleft()
    # G층에 도달한 경우 G층까지 도달하기 위해 버튼을 누른 횟수를 출력하고 BFS를 종료한다.
    if u == G:
        print(building[G])
        arrived = True
        break
    # 위로 U층을 가는 경우
    if u+U <= F and not visited[u+U]:
        queue.append(u+U)
        building[u+U] = building[u] + 1
        visited[u+U] = True
    # 아래로 D층을 가는 경우
    if u-D >= 1 and not visited[u-D]:
        queue.append(u-D)
        building[u-D] = building[u] + 1
        visited[u-D] = True
# 만약 BFS 시행 중에 G층에 도달하지 못한 경우 'use the stairs'를 출력한다.
if not arrived:
    print("use the stairs")