백준 5014번 - 스타드 링크

출처 : 5014번: 스타트 링크 (acmicpc.net)

5014번: 스타트링크

---

스타트 링크

한국어   

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

1 초

256 MB

21530

7164

5409

34.280%

문제

강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트 링크가 있는 건물에 늦게 도착하고 말았다.

스타트 링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트 링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다.

보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없다. U버튼은 위로 U층을 가는 버튼, D 버튼은 아래로 D층을 가는 버튼이다. (만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다)

강호가 G층에 도착하려면, 버튼을 적어도 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오. 만약, 엘리베이터를 이용해서 G층에 갈 수 없다면, "use the stairs"를 출력한다.

입력

첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.

출력

첫째 줄에 강호가 S층에서 G층으로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 출력한다. 만약, 엘리베이터로 이동할 수 없을 때는 "use the stairs"를 출력한다.

 

---

[ 문제 해설 ]

 

1. f, s, g, u, d 입력을 받고

2. dfs를 이용하여 조건에 맞게 작동하도록 합니다.

 

up을 했을 경우, 업이 f 층을 넘어서는 안 되는 한에 올라가야 하고, 마차 나지로 down을 할 때 지하층으로 내려가지 않는 선에 하에 내려가야 한다. 이런 조건을 조건문에 명시화 하면서 dp를 이용하여 기록하면서 dfs 탐색을 하면 어렵지 않게 원하는 결과를 얻을 수 있습니다.

 

---

 

[ 코드 ]

 

from collections import deque
import sys
input = sys.stdin.readline


def bfs():
    q = deque([s])
    print(q)
    dp[s] = 1
    while q:
        start = q.popleft()
        if start == g:
            print(dp[g] - 1)  # 1 부터 시작하니까 끝날 때는 -1을 해주는 것
            return

        up = start + u
        down = start - d
        if up <= f and not dp[up]:
            q.append(up)
            dp[up] = dp[start] + 1
        if down > 0 and not dp[down]:
            q.append(down)
            dp[down] = dp[start] + 1

    else:
        print("use the stairs")
        return


f, s, g, u, d = map(int, input().split())
dp = [0] * (f + 1)
bfs()

 

---

후기

 

이 문제는 기존적인 탐색 알고리즘을 활용할 수 있게 

해주는 문제로 생각된다.