[백준/5014/파이썬] 스타트링크

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

5014번: 스타트링크

Problem

강호가 G층에 도착하려면 ,버튼을 적어도 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오.

 

조건

• F : 건물의 층수, S : 현재 위치, G : 목표 위치, U : 위로 U 층 가는 버튼, D : 아래로 D 층 가는 버튼
• 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.

SOL)

 

항상 2차원 맵에서 경로 찾기를 하다가, 갑자기 생소하게 1차원 배열을 가지고 놀아야한다.

처음에는 이게 BFS인가 싶었지만, BFS/DFS로 시뮬레이션을 한다고 생각하고 , 구현해 보았다.

그리고, 선형탐색으로 한다면, 최소횟수가 보장이 어렵기 때문에, BFS가 적절해 보인다.

구현로직은, BFS를 사용하면, 최단거리가 보장되기 때문에, 각 층마다, 방문여부를 체크해주고, 방문하지 않았다면, 있었던 층에 도달하기 위한 횟수 + 1 을 해주면 된다. 그리고, G층에 도착하면, 해당 층의 거리 값을 출력해주면 끗.

 

from collections import deque
# F : 건물의 층수
# S : 현재 위치
# G : 목표 위치
# U : 위로 U 층 가는 버튼
# D : 아래로 D 층 가는 버튼
# 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.
# zero -base로 했음. 1층 베이스로 하면 더 빠르긴함.
F,S,G,U,D = map(int,input().split())
dq=deque()
building=[0]*F

def bfs():
    dq.append(S-1)
    building[S-1] = 1
    while dq:
        x = dq.popleft()
        if x==G-1:
            print(building[x]-1)
            return
        if x+U < F and not building[x+U]:
            dq.append(x+U)
            building[x+U]=building[x] +1
        if x-D >=0 and not building[x-D]:
            dq.append(x-D)
            building[x-D] = building[x] + 1
    print("use the stairs")
    return
bfs()