1697번 숨바꼭질 (python)

Problem

https://www.acmicpc.net/problem/1697

Solution

import sys
from collections import deque

def bfs(start, target):
    dq = deque()
    dq.append(start)

    dist = [0] * 100001

    while dq:
        idx = dq.popleft()
        if idx == target:
            return dist[idx]

        for next_idx in [idx - 1, idx + 1, idx * 2]:
            if 0 <= next_idx < 100001 and not dist[next_idx]:
                dist[next_idx] = dist[idx] + 1
                dq.append(next_idx)

N, K = map(int, sys.stdin.readline().split())

print(bfs(N, K))

-1로 이동하는 경우로 인해 dfs로 접근하였더니 RecursionError가 발생하였다.

bfs를 통해 한 단계씩 접근하고 제일 먼저 target에 접근할 때 해당 단계를 반환하였다.
dist를 이용하여 인덱스별로 접근한 단계를 기록하였다. 단계별로 접근하기 때문에 이미 0이 아닌 값이 들어가있다면 이전 단계에서 접근한 것이므로 예외처리를 한다. 처음에 이 예외처리가 없었더니 메모리초과가 발생하였다.

Reference

https://tooo1.tistory.com/111