[백준/5014/파이썬] 스타트링크

소스코드

from collections import deque

F,S,G,U,D = map(int,input().split())

def bfs(start):

  queue = deque([start])

  visited[start] = 1                    # 처음시작한 층수를 1로 해줘야 재방문 안함 

  while queue : 

    start = queue.popleft()

    if start == G:                        # 목표 도달

      return count[G]

    for i in (start+U, start-D):

      if (0 < i <= F) and not (visited[i]): 

        queue.append(i)

        visited[i] = 1

        count[i] = count[start] + 1

  if count[G] == 0:

    return "use the stairs"

visited = [0 for i in range (F+1)]    # 층수마다 방문여부

count = [0 for i in range (F+1)]     # 층수마다 몇번 걸렸는지

print(bfs(S))

알고리즘

숨바꼭질 문제와 비슷하게 풀 수 있는 문제인것 같다.

각 층수에 대해 visited[] 리스트를 선언하고 방문하면 1로 갱신하여 queue에 다시 안 들어가게 설정을 한다.

또한 각 층수에 대해 count[] 리스트로 몇번 이동하면 방문할 수 있는지도 선언해준다.

(5층-> 6층 :

visited[5] = 1 visited[6] = 0 count[5]=4 

                => visited[6] = 1 count[6]=5 )

즉 5층까지 가는데 4번 방문을 했어야하면 다음층은 5번 방문하면 된다는 소리이다.

방문안한 층수에 대해 queue에 삽입해나가며 실행하면 된다.