[BOJ] 1697 / 숨바꼭질 / python 파이썬

[BOJ] 1697 / 숨바꼭질 / python 파이썬

[BOJ] 1697 / 숨바꼭질 / python 파이썬

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

1697번: 숨바꼭질

 

풀이

최단시간으로 도달하는 문제이기 때문에 BFS 로 풀이 하였다.

 

처음 시도에는 단순히 모든 경우의수를 탐색하였기 때문에, 메모리 초과가 발생 하였다.

 

방문했던 위치에 재방문 하는 경우의수를 고려하여 해결하였다.

 

from collections import deque

N, K = map(int, input().split())

# 1초 후에 X-1 또는 X+1로 이동하게 된다.
# 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

queue = deque()
queue.append(N)

MAX = 100000

time = [0] * 100001
time[N] = 0

while True:
    Q = queue.popleft()

    if Q == K:
        print(time[Q])
        break

    if Q+1 <= MAX and not time[Q+1]:
        time[Q+1] = time[Q]+1
        queue.append(Q+1)
    if Q-1 >= 0 and not time[Q-1]:
        time[Q-1] = time[Q]+1
        queue.append(Q-1)
    if Q*2 <= MAX and not time[Q*2]:
        time[Q*2] = time[Q]+1
        queue.append(Q*2)

 

 

---

참고 블로그

https://deepwelloper.tistory.com/entry/BOJ-1697-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88-%ED%8C%8C%EC%9D%B4%EC%8D%ACPython-%ED%92%80%EC%9D%B4

[BOJ 1697] 숨바꼭질 파이썬(Python) 풀이