[백준 - Python] 5014. 스타트링크 (DFS/BFS)

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

5014번: 스타트링크

 

코드

from collections import deque
import sys
input = sys.stdin.readline
# f : 건물 높이 , s : 강호 현재 위치 , g : 목표 위치, u : 위로 , d : 아래로
f, s, g, u, d = map(int, input().split())
visited = [0] * (f+1)

def bfs(start, cnt):
    q = deque([start])
    visited[start] = 1
    while q:
        x = q.popleft()
        if x == g:
            return visited[g] - 1
        for i in (x + u, x - d):
            if 1 <= i <= f and not visited[i]:
                visited[i] = visited[x] + 1
                q.append(i)
    return "use the stairs"

print(bfs(s, 0))

 

bfs를 활용해서 풀었고,

탐색을 하다가 목표하는 층에 도달했을 때

반복문을 탈출하고 bfs를 종료한다.

 

방문 여부를 확인하는 visited 리스트에

목표 층까지 이동하는데 눌러야 하는 버튼의 횟수를 저장하였다.

 

넓이 우선 탐색인 BFS를 사용했기 때문에,

탐색을 하면서 가장 먼저 도달하였을 때가 최솟값이었다.

 

해당 지점에서 U, D 버튼을 눌러서 갈 수 있는 위치를

튜플로 묶어서 순회하는 객체로 사용했다.

 

이동하려는 층이 존재하는 층이면서 방문한 적이 없는 층이라면,

지금까지의 이동 횟수에 1을 더한 값을 저장해주고,

큐에 해당 층을 넣어준다.

 

반복문 안에서 목표 지점 도달에 실패한 경우에

실패 메세지를 출력하도록 했다.