[백준] 12851 숨바꼭질 2 python

www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

from collections import deque
n, k = map(int, input().split())
if n == k:
    print(0)
    print(1)
else:
    dp = [0] * 100001
    q = deque([n])
    dp[n] = 1
    size, depth, cnt = len(q), 0, 0
    if_chk = True
    limit = 100000
    result_val = 0
    while q:
        if cnt == size:
            cnt = 0
            size =len(q)
            depth += 1
        cnt += 1
        x = q.popleft()
        if 0 <= x - 1 and (dp[x - 1] == 0 or dp[x - 1] == dp[x] + 1):
            dp[x - 1] = dp[x] + 1
            q.append(x - 1)
            if x - 1 == k:
                result_val += 1
        if x + 1 <= 100000 and (dp[x + 1] == 0 or dp[x + 1] == dp[x] + 1):
            dp[x + 1] = dp[x] + 1
            q.append(x + 1)
            if x + 1 == k:
                result_val += 1
        if x <= 50000 and (dp[2 * x] == 0 or dp[x * 2] == dp[x] + 1):
            dp[2 * x] = dp[x] + 1
            q.append(2 * x)
            if x * 2 == k:
                result_val += 1
        if if_chk and dp[k]:
            if_chk = False
            limit = dp[k] - 1
        if depth >= limit:
            break
    # result = limit
    print(limit)
    print(result_val)

이전글과 같은문제인데 구해야할게 하나 더 생겼다.

최소이동으로 갈수 있는 방법의 갯수까지 알아야한다.

같은 문제여서 그대로 복사해서 사용했는데 뭔가더 돌아간듯한 느낌이다.

이전과 다른점은 dp에 값이 있어도 확인하는 조건이 추가되었다.

그리고 limit을 정해서 최소 거리를 찾게 되면 딱 depth 까지만 확인한다.

---

타인의 코드를 보니 time을 따로 잡고 dp로 주는 값을 그 곳까지 가는 경우의 수로 잡았다.

창을 꺼버려서 가져오긴 귀찮지만 속도도 빠르고 꽤 좋은 코드였다.