[Python] 백준 5014번 - 스타트링크

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

5014번: 스타트링크

 

1697번 숨바꼭질 문제랑 알고리즘이 거의 같았다.

2021.07.12 - [Coding/백준] - [Python] 백준 1697번 - 숨바꼭질

비슷한 구조의 bfs문제를 한 번 더 풀 수 있어서 bfs 이해하는데 더 도움이 됐다.

 

count를 처음에는 그냥 변수로 만들어서 갱신해줬는데 그렇게 하다보니 갈라지는 부분이라고 해야하나... 쨌든 그런 곳에서 count가 여러 개로 나뉘어져야 하는데 변수 하나로 만들었기 때문에 코드를 완성할 수 없었다.

그래서 count도 visited 처럼 리스트로 만들었다.

 

엘리베이터를 타고 목적지에 갈 수 없는 경우에 "use the stairs"를 출력해야 한다.

이런 예외 경우는 코드를 다 작성한 후 마지막 부분에 추가를 해주는데, 이때 조건을 찾는 게 항상 어렵다.

이번에도 그냥 count[G]가 갱신되지 않고 처음 초기화된 0의 상태라면 엘리베이터를 타고 도착하지 못한 것이므로 이것을 조건으로 주면 되는데, 자꾸 조건을 어렵게 생각한다.

예외로 생각하지 않고, 또 하나의 경우로 생각해서 더 어렵게 접근하는 것 같다.

그래서 이 부분 조건을 모르겠어서 구글링을 통해 힌트를 얻었다.

 

예제가 다 잘 돌아가서 처음 제출했는데 에러가 났다.

조건이나 인덱스를 잘못 설정해준 줄 알았는데 알고보니 bfs함수 들어가자마자 첫 v에 대해 visited[v] = 1 을 안 해줬었다. 이런 거.. 놓치지 말자. ㅠ!

 

그래도 이 문제는 한 시간 안 걸려서 풀었다....

매일매일 한 문제씩 시도는 하는데 하루 안에 안 끝나는 문제들이 많아서 ㅋㅋㅋ

더 열심히 해야지.......

import sys
from collections import deque

def bfs(v):
    q = deque([v])
    visited[v] = 1
    while q:
        v = q.popleft()
        if v == G:
            return count[G]
        for i in (v+U, v-D): #U만큼 위로 or D만큼 아래로
            if 0 < i <= F and not visited[i]:
                visited[i] = 1
                count[i] = count[v] + 1
                q.append(i)
    if count[G] == 0:
        return "use the stairs"

input = sys.stdin.readline
F, S, G, U, D = map(int, input().split())
visited = [0 for i in range(F+1)]
count = [0 for i in range(F+1)]
print(bfs(S))