[Python] 12761번 돌다리

✏️ 문제

 

문제 파악

최소한의 이동 횟수를 출력하라 했으므로 BFS를 사용하여 푼다.

동규가 현재 위치에서 다음 위치로 갈 수 있는 방법은 8가지가 있다.

1. 현재 위치 - 1
2. 현재 위치 + 1
3. 현재 위치 - A
4. 현재 위치 + A
5. 현재 위치 - B
6. 현재 위치 + B
7. 현재 위치 * A
8. 현재 위치 * B

현재 위치에서 위 8가지의 다음 위치를 덱에 넣는 방법은 다음과 같다.

for next_v in (v-1, v+1, v-a, v-b, v+a, v+b, v*a, v*b):
    q.append(next_v)

 

이렇게 for 문을 만들면 next_v에 8가지의 v의 다음 위치가 차례대로 대입하게 된다.

 

처음엔 graph와 visited 배열의 크기를 주미의 위치까지만 만들었는데 생각해보니 주미의 위치보다 더 멀리갔다가 다시 돌아오는 경우도 있는 것 같아 크기를 n과 m의 최대값인 100000으로 바꿨다.

 

알고리즘

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

 

 

코드

from collections import deque
import sys
input = sys.stdin.readline

a, b, n, m = map(int, input().split())
graph = [0] * 100001
visited = [0] * 100001

def bfs(v):
  q = deque([v])
  visited[v] = 0

  while q:
    v = q.popleft() 

    for next_v in (v-1, v+1, v-a, v-b, v+a, v+b, v*a, v*b):
      if 0 < next_v < 100001 and visited[next_v] == 0:
        visited[next_v] = visited[v] + 1
        q.append(next_v)

bfs(n)
print(visited[m])

 

 

---

 

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

[알고리즘] DFS와 BFS