[백준/파이썬] 5014번: 스타트링크 (BFS a.k.a 너비우선탐색)

요즘은 백준 인기문제집에 있는 'DFS+BFS 필수 문제' 문제집을 풀고 있어요.

1679번 숨바꼭질 문제보다는문제 조건도 쉽고 BFS의 개념이나 시간복잡도를 이해하기 쉬워보이는 문제라 가져와봤어요.

 

BFS 개요 (출처: google)

-문제

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

5014번: 스타트링크

 

-풀이: BFS(너비우선 탐색)

현재 위치하고 있는 층에서 이동할 수 있는 경우의 수 두가지(+u, -d)를 중복되지 않게 조사해요.

deque를 import 해서 선입선출식으로 데이터를 조사해요.

이때 deque에는 (조사하는 층, 이동에 걸린 횟수)를 대입해서 층 정보와 횟수 정보를 함께 담아요.

 

그 후 bfs함수는 다음과 같이 행동해요

-그 와중에 목표로 하고 있는 g층에 도착한다면 중지하고 튜플에 같이 저장해놓았던 이동 횟수를 출력해요

-찾지 못한다면 1층~F층까지 모든 탐색이 완료될 때까지 기다린 후 -1을 return하게 해요.

 

중복을 제한했기에 bfs의 최대 연산 횟수는 건물의 층수인 f, 즉 100만번에 지나지 않아요.

그렇기에 bfs 내부 연산이 O(n) 이상이 아니라면 무난히 풀이를 할 수 있어요!

 

-소스코드

f, s, g, u, d = map(int, input().split())

from collections import deque

def bfs():
    visited = [0] * f
    elv = deque([(s, 0)])
    visited[s-1] = 1
    while elv:
        
        a = deque.popleft(elv)
        if a[0] == g:
            return a[1]
            
        else:
            if a[0] + u <= f and not visited[a[0]+u-1]:
                elv.append((a[0]+u , a[1] + 1))
                visited[a[0]+u-1] = 1
            if a[0] - d >0 and not visited[a[0]-d - 1]:
                elv.append((a[0]-d , a[1] + 1))
                visited[a[0]-d-1] = 1
    return -1
result = bfs()
if result == -1:
    print('use the stairs')
else:
    print(result)