📚 5014 - 스타트링크

스타트링크

이해

이번 문제는 전형적인 너비 우선 탐색 문제이다.
이와 같이 총 길이가 나와 있고, 시작점과 도착점 그리고 증가와 감소가 나와있을 경우 너비 우선 탐색을 사용하면 된다.

다만, 나도 이것 때문에 틀렸었는데

10 10 10 1 2 => 0

10 1 10 0 1 => use the stairs

무조건 경우의 수가 존재하지 않는다고 use the stairs를 출력하면 틀린다!
위와 같은 경우의 수도 체크해야 한다.

소스

from collections import deque
import sys

read = sys.stdin.readline

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

visited = [False] * (f + 1)

ud = [u, d * -1]


def bfs():
    q = deque()
    q.append((s, 0))
    global result

    visited[s] = True
    while q:
        cur_data, cnt = q.popleft()

        if cur_data == g:
            result = cnt
            return True

        for i in ud:
            next_layer = cur_data + i

            if 1 <= next_layer <= f and not visited[next_layer]:
                visited[next_layer] = True
                q.append((next_layer, cnt + 1))

    return False


result = 0

if bfs():
    print(result)
else:
    print("use the stairs")

채점 결과