[백준] 12761 돌다리 with Python

📌 BOJ 12761 돌다리

💡 조건

1. 돌의 번호는 0 부터 100,000 까지 존재하고 동규는 N번 돌 위에, 주미는 M번 돌 위에 위치하고 있다.

2. 동규는 주미가 너무 보고싶기 때문에 최대한 빨리 주미에게 가기 위해 A, B 만큼의 힘을 가진 스카이 콩콩을 가져왔다.

3. 현 위치에서 +1칸, -1칸을 이동할 수 있고, 스카이 콩콩을 이용해 현 위치에서 A나 B만큼 좌우로 점프할 수 있으며,
   순간적으로 힘을 모아 현 위치의 A배 나 B배의 위치로 이동을 할 수 있다.

4. 이동 과정에서 100,000보다 크거나 0보다 작은 번호의 돌은 존재하지 않으므로 갈 수 없고,
   같은 방법을 계속 사용해도 되며 항상 도달할 수 있는 케이스만 주어진다.

5. 첫 줄에 스카이 콩콩의 힘 A와 B, 그리고 동규의 현재위치 N, 주미의 현재 위치 M이 주어진다.
   (단, 2 <= A, B <= 30 이고 0 <= N, M <= 100,000)

6. 다이나믹프로그래밍 유형의 문제

🖥 소스 코드

from sys import stdin
from collections import deque

a, b, n, m = map(int, stdin.readline().split())
dp = [-1 for _ in range(100001)]


def solve():
    q = deque()
    q.append(n)
    dp[n] = 0
    while q:
        x = q.popleft()
        for i in (x * a, x * b, x + a, x - a, x + b, x - b, x + 1, x - 1):
            if 0 < i < 100001:
                if dp[i] == -1:
                    dp[i] = dp[x] + 1
                    q.append(i)


solve()
print(dp[m])

🔖 예제 및 실행결과

예제

3 7 2 98500

실행결과

10

⌨️ 문제 풀이

1. -1로 채워진 dp 리스트를 생성한다. 이미 방문했던 돌다리는 건너지 않을 것이다.
   즉, -1이 아닌 돌다리만 밟고 갈 것이다. 현재 위치 n은 0으로 갱신해준다.
   또한 큐에 n을 넣어 이동을 시작한다.

2. 조건 (3)번에 써놓았던 이동이 가능한 경우의 계산값을 순회하면서 0 과 100000 값 사이에 있는지 확인한다.

3. (2)번의 조건에 해당한다면, dp[i] 의 값을 현재 위치에 해당하는 이동 값에서 + 1한 값을 저장해준다.

4. 이동할 돌다리의 번호를 큐에 넣어준다.

5. 큐가 비어서 끝나게 되면, N에서 출발하여 M까지 가는 최소 이동횟수 dp[M]을 출력한다.

💾 느낀점

1. 숨바꼭질과 비슷한 느낌. 수평으로 좌표이동을 한다고 생각하고 풀이하니 쉽게 풀렸다.