[Python] 5014번 스타트링크

✏️ 문제

 

문제 파악

버튼 수의 최솟값을 구하므로 BFS를 활용해서 풀었다.

 

다음 층이 해당 층 + u 또는 해당 층 - d 두 가지로 나뉘므로 다음과 같이 코드를 구현했다.

그리고 버튼의 수를 저장하기 위해 다음 층 = 해당 층 + 1 를 하였다.

for next_node in (node+u, node-d):
  if 0 < next_node <= f and graph[next_node] == 0:
    q.append(next_node)
    graph[next_node] = graph[node] + 1

 

예제는 잘 돌아가는데 틀렸습니다가 뜨는 경우 가장 아래의 층이 0이 아니라 1인 지 확인해보길..!

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

 

 

코드

from collections import deque

f, s, g, u, d = map(int, input().split())
graph = [0] * (f+1)

def bfs(v):
  q = deque([v])
  graph[v] = 1
  
  while q:
    node = q.popleft()

    if node == g:
      return graph[g] - 1

    for next_node in (node+u, node-d):
      if 0 < next_node <= f and graph[next_node] == 0:
        q.append(next_node)
        graph[next_node] = graph[node] + 1

  return 'use the stairs'   

print(bfs(s))

 

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS