Algorithm PS/BOJ
[BOJ] 1697 / 숨바꼭질 / python 파이썬
migrationArc
2021. 7. 25. 18:38
[BOJ] 1697 / 숨바꼭질 / python 파이썬
https://www.acmicpc.net/problem/1697
1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
풀이
최단시간으로 도달하는 문제이기 때문에 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)
참고 블로그
[BOJ 1697] 숨바꼭질 파이썬(Python) 풀이
문제보기 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수..
deepwelloper.tistory.com