5014 - 스타트링크
📚 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")
채점 결과
Author And Source
이 문제에 관하여(5014 - 스타트링크), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@chang626/5014-스타트링크저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)