[Python | 5014] 스타트링크

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

---

문제 설명

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

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

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

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

 

📌 시간 제한: 1초

---

입력

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

---

출력

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

---

문제 접근

회사에 출근하려는데 엘리베이터 버튼이 일부 고장 난 상황을 모델링한 문제로, 현재 층(S)에서 목표 층(G)까지 이동하는 최소 횟수를 구하는 문제다. 버튼은 위로 U층, 아래로 D층 이동하는 기능만 존재하며, 건물은 총 F층이다.

 

 

이 문제는 버튼을 눌러 도달 가능한 모든 경우의 수를 탐색하고, 그중 최소 횟수를 구해야 한다. 즉, "어떻게 하면 최소한의 버튼 조작으로 목적지에 도달할 수 있을까?"를 묻는 전형적인 최단 거리 탐색 문제이다.

• 상태(state): 현재 위치한 층 (1부터 F까지)
• 행동(action): U층 위로 올라가기 또는 D층 아래로 내려가기
• 조건(condition): 1층보다 작거나 F층보다 큰 곳으로 이동할 수 없음

이 문제의 핵심은 층을 노드로 보고, U 또는 D를 누르면 이동 가능한 이웃 노드로 간선이 연결된 것처럼 생각하는 것이다. 
각 상태(층)에서 이동할 수 있는 다음 상태로 가는 데 드는 비용이 모두 1로 동일하며, 최단 경로를 구해야 하는 경우에는 BFS(너비 우선 탐색)이 가장 적절한 알고리즘이다.

구현

• 방문 여부를 체크하기 위한 visited 배열과, 현재 층까지 몇 번 버튼을 눌렀는지를 저장할 dist 배열을 사용
• 시작 층 S에서 BFS를 시작하며, 위(U) 혹은 아래(D)로 이동 가능한 층을 큐에 넣음
• 이미 방문한 층은 다시 큐에 넣지 않도록 하여 중복 방문을 방지
• BFS 도중 목표 층 G에 도달하면 그 시점의 dist[G]를 반환
• 끝까지 탐색해도 도달하지 못하면 "use the stairs"를 출력

from collections import deque

def bfs(F, S, G, U, D):
    visited = [False] * (F + 1)    # 방문 여부 기록
    dist = [0] * (F + 1)           # S층에서 해당 층까지 도달하는 데 걸린 버튼 횟수

    queue = deque([S])
    visited[S] = True

    while queue:
        curr = queue.popleft()

        if curr == G:             # 목표 층에 도달하면 버튼 횟수 반환
            return dist[curr]

        # 다음에 이동할 수 있는 두 층: U층 위로 or D층 아래로
        for next_floor in (curr + U, curr - D):
            if 1 <= next_floor <= F and not visited[next_floor]:
                visited[next_floor] = True
                dist[next_floor] = dist[curr] + 1
                queue.append(next_floor)

    return "use the stairs"       # 모든 경우를 탐색해도 도달할 수 없는 경우

F, S, G, U, D = map(int, input().split())
print(bfs(F, S, G, U, D))

 

 

⏱ 시간 복잡도

• 상태 공간: 1층부터 F층까지 총 F개의 노드
• 최악의 경우: 모든 층을 한 번씩 방문하며 탐색 → O(F)
• F의 최대값이 1,000,000이라면 1백만번 이하의 연산

또한, BFS 특성상 목표 층(G)에 처음 도달하는 순간이 가장 빠른 경로이기 때문에, 이후의 경로를 더 확인할 필요도 없다.