[백준] 1697. 숨바꼭질 - 파이썬

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

1697번: 숨바꼭질

 

난이도에 맞지 않게 굉장히 애를 먹었던 문제.

시간초과 메모리초과 틀렸습니다의 늪에서 허우적거린...^ㅁ^ 풀고 보니 결국 하나를 잘못 생각했다.

 

풀이 1

[백준] 1463. 1로 만들기 와 비슷하게, DP로 풀 수 있을 것이라 생각했으나, 오답.

아무래도 +1, -1이 둘 다 존재하기 때문에, 수가 계속 커지기만 하는 것은 아니라서, 이런 방식으로 풀이하는 것은 불가능한 듯.

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

dp = dict()
dp[K] = 0
dp[K*2] = 1

for i in range(K*2, 0, -1):
    if i % 2 == 0:
        dp[int(i/2)] = min(dp.get(int(i/2), 100000), dp[i]+1)
    dp[i+1] = min(dp.get(i+1, 100000), dp[i]+1)
    dp[i-1] = min(dp.get(i-1, 100000), dp[i]+1)

print(dp[N])

 

풀이 2

BFS같은 느낌으로 풀었으나, visit check를 하지 않아서 그런지 메모리 초과가 난다.

 

from collections import deque
N, K = map(int, input().split())

deq = deque([N])
nowDeq = deq

cnt = 0
isFind = False


while not isFind:
    deq = deque([])
    while nowDeq:
        a = nowDeq.popleft()
        if a == K:
            print(cnt)
            isFind = True
            break

        deq.append(a*2)
        deq.append(a+1)
        deq.append(a-1)

    cnt += 1
    nowDeq = deq

 

풀이 3

시간초과, 메모리초과의 늪에서 만들어낸 답(?)

visit처리 해주고, 주의할 점은.. indexError 나지 않도록 0~100,000 사이로 조건 걸어줍시다.

 

from collections import deque
import sys
input = sys.stdin.readline

def sol():

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

    deq = deque([N])
    visit = dict()
    visit[N] = 0
    while deq:
        a = deq.popleft()
        if a == K:
            print(visit[a])
            return

        for i in [a*2, a+1, a-1]:
            if 0 <= i <= 100000 and visit.get(i, -1) == -1:
                deq.append(i)
                visit[i] = visit[a]+1

sol()