BOJ 1697 숨바꼭질

https://www.acmicpc.net/problem/1697
시간 2초, 메모리 128MB
input :

• N K(0 ≤ N, K ≤ 100,000)

output :

• 찾는 가장 빠른 시간을 출력

조건 :

• 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동

---

수빈이가 움직이는 경우는 즉.
x + 1
x - 1
x * 2

이다. 그리고 이동한 경우가 0 ~ 100,000 사이여야 한다.
q에 이 정보를 다 넣어가며 계산을 하는 것은 메모리 초과가 발생하니 dp를 이용해서 visit도 나타낼 겸 쓰도록 하자.

그리고 언제나 bfs를 이용해서 k 지점을 제일 처음 만나는 상태가 가장 빠른 시간이므로. k와 같은 값을 만나면 break를 걸자.

import sys
from _collections import deque

n, k = map(int, sys.stdin.readline().split())
dp = [0] * (100001)

q = deque([])
q.append((n, 1))

while q:
    now, cnt = q.popleft()
    dp[now] = cnt
    
    if now == k:
        break

    if now - 1 >= 0 and dp[now - 1] == 0:
        q.append((now - 1, cnt + 1))
    if now * 2 <= 100000 and dp[now * 2] == 0:
        q.append((now * 2, cnt + 1))
    if now + 1 <= 100000 and dp[now + 1] == 0:
        q.append((now + 1, cnt + 1))


print(dp[k] - 1)

위의 코드로 하면 1044ms가 걸리는데.

import sys
from _collections import deque

n, k = map(int, sys.stdin.readline().split())
dp = [0 for i in range(100001)]

q = deque([])
q.append((n, 1))

while q:
    now, cnt = q.popleft()
    dp[now] = cnt

    if now == k:
        break

    if now - 1 >= 0 and dp[now - 1] == 0:
        dp[now - 1] = cnt + 1
        q.append((now - 1, cnt + 1))
    if now * 2 <= 100000 and dp[now * 2] == 0:
        dp[now * 2] = cnt + 1
        q.append((now * 2, cnt + 1))
    if now + 1 <= 100000 and dp[now + 1] == 0:
        dp[now + 1] = cnt + 1
        q.append((now + 1, cnt + 1))

print(dp[k] - 1)

이 코드를 쓰면.
꼭 pop을 해서 업데이트 하는 것이 아니라, q에 append할 때 dp를 업데이트 하도록 하니까 메모리도 적게 쓰고,,, 시간도 적게 쓴다 ;;;