[BOJ/백준] 5014번 스타트링크 | BFS | 파이썬

문제

풀이

from collections import deque

F, S, G, U, D = map(int, input().split())
visited = [0] * (F + 1)

def bfs(visited, v):
    queue = deque([v])
    dx = [U, - D]
    while queue:
        x = queue.popleft()
        if x == G:
            break
        for i in range(len(dx)):
            # 해당하는 층이 없을 때 움직이지 않는다
            if dx[i] == 0:
                continue
            nx = x + dx[i]
            if 0 < nx <= F and not visited[nx]:
                visited[nx] = visited[x] + 1
                queue.append(nx)
if S == G:
    print(0)
else:
    bfs(visited, S)
    if visited[G]:
        print(visited[G])
    else:
        print('use the stairs')

현재 위치에서 스타트 링크의 위치까지, 가까운 곳 부터 방문하며 최단거리(버튼을 적어도 몇 번 눌러야 하는지)를 확인해야한다. 즉 1차원 BFS문제이다. 

 

주의해야할 점

- 현재 위치와 스타트 링크의 위치가 같은 경우 > 엘리베이터 버튼을 누르지 않아도 된다.

- U또는 D가 0인 경우  > 역시 엘리베이터 버튼을 누르지 않아도 된다(반복문에서 continue)

 

 

---

5014번: 스타트링크

okky에서 알고리즘 스터디를 구했다. 이제 알고리즘 풀이도 외롭지않아😇