[BOJ / 백준] 1697번 숨바꼭질 파이썬(Python) 문제 풀이

문제

 

문제 링크 : https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

 

 

 

CODE

from collections import deque


def solve(n, k):
    time = [0] * (200001)
    q = deque([n])
    time[n] = 0

    while q:
        now = q.popleft()
        if now == k:
            print(time[k])
            return

        if abs(k - now) > abs(k - 2 * now) and time[2 * now] == 0:
            q.append(2 * now)
            time[2 * now] = time[now] + 1

        if now + 1 <= 100000 and time[now + 1] == 0:
            q.append(now + 1)
            time[now + 1] = time[now] + 1

        if now - 1 >= 0 and time[now - 1] == 0:
            q.append(now - 1)
            time[now - 1] = time[now] + 1


n, k = map(int, input().split())
solve(n, k)

 

 

 

 

 

풀이

💡 idea

- 시간 증가에 가중치가 없고 최단 시간을 찾는 문제이므로 BFS로 풀자!

 

 

💡 implementation

- Index Error 때문에 여러 번 틀렸다,,,

    * 문제의 힌트처럼 K 넘어서까지 이동해서 가는 경로가 최소일 때가 있으므로 time의 크기는 넉넉하게 MAX * 2

    * X2를 하는 순간이동은 이동했을 때 동생이랑 더 가까워지는 경우에만 하도록

    * +1 / -1 이동 또한 제한범위를 넘지 않도록

        if abs(k - now) > abs(k - 2 * now) and time[2 * now] == 0:
            q.append(2 * now)
            time[2 * now] = time[now] + 1

        if now + 1 <= 100000 and time[now + 1] == 0:
            q.append(now + 1)
            time[now + 1] = time[now] + 1

        if now - 1 >= 0 and time[now - 1] == 0:
            q.append(now - 1)
            time[now - 1] = time[now] + 1

 

 

 

 

 

 

결과