문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
예제 입력 / 출력
5 17
4
힌트
수빈이가 5 → 10 → 9 → 18 → 17 순으로 가면 4초 만에 동생을 찾을 수 있다.
첫 풀이 (메모리 초과)
처음에는 큐에 [위치, 시간]을 저장하면서 BFS를 구현하였다. 로컬에서 실행했을 때 알맞은 값이 나왔지만 채점해보니 메모리 초과가 발생하였다.
from collections import deque
def solution(ap, bp):
queue = deque([[ap, 0]])
time = 0
def move(p, t):
if p - 1 >= 0:
queue.append([p - 1, t + 1])
queue.append([p + 1, t + 1])
queue.append([p * 2, t + 1])
return
while queue:
[p, t] = queue.popleft()
if p == bp:
return t
if t == time:
move(p, t)
elif t > time:
queue.appendleft([p, t])
time += 1
return move(ap, 0)
ap, bp = map(int, input().split())
print(solution(ap, bp))먼저 방문 체크가 없어서 같은 위치를 여러 번 큐에 넣은 것이 잘못되었다. 또한 시간 비교를 위해 (위치, 시간)을 꺼냈다가 다시 집어 넣었는데 BFS이므로 큐가 레벨 순서를 보장한다는 점을 놓쳐 불팔요하게 appendleft를 하였다. 마지막으로 범위에 제한을 두지 않아 p*2 연산으로 인해 큐에 끝없이 큰 값이 들어가면서 메모리를 과도하게 사용하였다.
개선된 풀이
- 방문 여부 체크: 이미 방문한 위치는 다시 큐에 넣지 않는다.
- 시간은 큐에 함께 저장: appendleft 제거
- 범위 제한 추가: 0 ≤ p ≤ 100000 범위 내에서 탐색
from collections import deque
def solution(ap, bp):
MAX = 100000
visited = [False] * (MAX + 1)
queue = deque([(ap, 0)])
visited[ap] = True
while queue:
p, t = queue.popleft()
if p == bp:
return t
for np in (p - 1, p + 1, p * 2):
if 0 <= np <= MAX and not visited[np]:
visited[np] = True
queue.append((np, t + 1))
ap, bp = map(int, input().split())
print(solution(ap, bp))