[BOJ 1697] 숨바꼭질(Python)

문제링크

숨바꼭질

풀이 전 계획 및 생각

bfs를 이용해서 문제를 풀기로 결정했다. 완전 탐색을 이용해서 전부 구해보면서 답을 찾는 방식을 사용했다.
현 위치에서 -1, +1, *2 한 위치를 다 보는 것이기 때문에, 각 노드마다 자식을 3개로 가지는 트리 구조를 생각했다.
이전 단계에서 다음 단계로 넘어갈 때, +1을 해주면서 횟수를 카운트했다.
이전에 풀었던 미로 탐색 문제와 비슷한 방식을 사용했다.

풀이

from collections import deque

MAX = 100001
n,k = map(int,input().split())
array = [0]*MAX

def bfs():
    q = deque([n])
    while q:
        now_pos = q.popleft()
        if now_pos == k:
            return array[now_pos]
        for next_pos in (now_pos-1,now_pos+1,now_pos*2):
            if 0 <= next_pos < MAX and not array[next_pos]:
                array[next_pos] = array[now_pos]+1
                q.append(next_pos)
print(bfs())

풀이하면서 막혔던 점과 고민했던 점

딱히 없었다.

풀이 후 알게된 개념과 소감

딱히 없었다.