[백준 5014 : PYTHON] 스타트링크

문제 풀기 : 5014번

5014번: 스타트링크

문제

스타트링크는 총 F층으로 이루어진 고층 건물이다. 스타트링크가 있는 곳의 위치는 G층이고 지금 있는 곳은 S층이다.

엘리베이터를 타고 G층으로 이동하려고 한다.

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

강호가 G층에 도착하려면, 버튼을 적어도 몇 번 눌러야 하는지 구한다.

만약, 엘리베이터를 이용해서 G층에 갈 수 없다면, "use the stairs"를 출력한다.

문제풀이

모든 경우의 수를 전부 찾는 완전탐색이면서 BFS를 사용한 문제이다.

현재 층에서 U(위), D(아래) 두 가지로 이동하는 경우의 수를 모두 큐에 넣어주어 해결하면 된다. 유의할 점은 큐에 넣는 데이터는 현재 층과 버튼을 누른 횟수이다.

또한 이미 방문한 층은 다시 방문하지 않도록 처리도 해주어야 한다.

코드 TIP

함수에서 리턴 값이 없을 경우 None값이 리턴된다.

전체코드

import sys
from collections import deque

def bfs():
    # 현재 층과 누적 버튼 수 저장하는 큐
    q = deque()
    q.append((S, 0))
    visited[S] = True

    while q:
        now, cnt = q.popleft()

        # 현재 층이 G층이라면 누적 버튼 수를 리턴
        if now == G:
            return cnt

        # U(위)버튼 누르는 경우의 수
        if now + U <= F and not visited[now + U] :
            q.append((now + U, cnt + 1))
            visited[now + U] = True

        # D(아래)버튼 누르는 경우의 수
        if now - D >= 1 and not visited[now - D] :
            q.append((now - D, cnt + 1))
            visited[now - D] = True


# 입력
F, S, G, U, D = map(int, sys.stdin.readline().split())

# 층 방문 여부
visited = [False for _ in range(F+1)]

# 출력
result = bfs()
print(result if result != None else "use the stairs")