[백준] 1697번: 숨바꼭질 Python 풀이

[백준] 1697번 숨바꼭질 Python 풀이

문제

 

백준 1697번 숨바꼭질 문제입니다.

 

이 문제를 처음 보았을 때는 DP로 풀어야겠다고 생각했습니다.

특정 지점에서 역으로 최단거리를 구하면 가볍게 DP로 풀 수 있을 거 같은데...

---

 

DP로 풀어보기

1. N >= K 일 때

일단 문제를 잘 살펴보면 $ 0<= N, K <= 100000 $인데

$ N < K $를 보장하지 않기 때문에 뒤로 가야 하는 상황이 존재합니다.

그런데 뒤로 가는 방법은 X-1 의 경우 밖에 없으니 $ N >= K $ 일 때 답은 $ N - K $입니다. 

2. N < K 일 때

DP로 풀기 위해서는 점화식을 잘 세워야 합니다.

일단 최소 거리를 구해야 하기 때문에 초기 값은 무한대로 설정하였습니다.

역으로 생각했을 때, 특정 지점 $X$로 갈 수 있는 방법은 $X-1$에서 한 칸 앞으로, $X+1$에서 한 칸 뒤로,

짝수일 때는 $X/2$ 에서 순간 이동하는 3가지가 존재합니다.

 

그래서 처음에는 점화식을

짝수의 경우 $DP[i] = min(DP [i+1] + 1, DP [i-1] + 1, DP [i/2] + 1)$

홀수의 경우 $DP[i] = min(DP [i+1] + 1, DP [i-1] + 1)$ 

 

로 해서 풀었습니다.

dp = [float('inf')] * (100000)
dp[n] = 0

for i in range(n+1, k+1) :
    if i % 2 == 0 :
        dp[i] = min(dp[i+1] + 1, dp[i-1] + 1, dp[i // 2] + 1)
    else :
        dp[i] = min(dp[i+1] + 1, dp[i-1] + 1)

 

그런데 이거 틀렸더라구요.

저렇게 풀면 3482 45592를 넣으면 637이 나와야 하는데 638이 나옵니다.

 

해당 풀이 방법은 2가지 문제가 있었습니다.

첫 번째로는 DP의 경우 과거의 데이터를 기반으로 새로운 값을 계산하는데

아직 계산되지 않은 미래의 값 $DP [i+1]$이 최소를 보장하지 않기 때문이고

 

두 번째는 점화식이 틀렸습니다.

목표 값이 짝수인 경우 최소 경로의 경우는 아래와 같이 2가지입니다.

뒤에서 오는 경우는 최소 경로가 아니네요.

 

따라서 짝수일 때 점화식은 $DP [i] = min(DP [i-1] + 1, DP[i / 2] + 1)$입니다.

4 → 8 을 가야하는 경우

홀수의 경우 순간이동을 해서 오는 바로 오는 최소 경로가 없고

뒤에서 X-1을 통해 오는 최소 경로가 존재합니다.

 

따라서 점화식은 $DP[i] = min(DP[i-1] + 1, DP [i+1] + 1)$입니다.

그런데 이때 $DP[i+1]$의 값은 미래의 값이기 때문에 사용하지 못합니다.

대신 순간이동하기 전의 짝수 값은 과거의 값이므로 사용가능합니다. 여기서 1을 더해주면 $DP[i+1]이 됩니다. 

따라서 $DP[(i+1)//2] + 1$을 사용해야 합니다.

 

따라서 홀수일 때 점화식은 $DP [i] = min(DP [i-1] + 1, DP[(i+1)//2] + 2)$입니다.

4 -> 7을 가야하는 경우

 

전체 코드는 다음과 같습니다.

import sys

input = sys.stdin.readline
n, k = map(int, input().strip().split(" "))

if n >= k :
    print(n-k)
    exit()

else :
    dp = [float('inf')] * (1000000)
    dp[n] = 0

    # N보다 작을 때는 뒤로가기
    for i in range(0, n) :
        dp[i] = n - i
    
    # K가 N보다 클 때
    for i in range(n+1, k+2) :
        if i % 2 == 0 :
            dp[i] = min(dp[i//2] + 1, dp[i-1] + 1)

        else :
            dp[i] = min(dp[i-1] + 1, dp[(i+2)//2] + 2)

    print(dp[k])

---

BFS로 풀어보기

이 문제는 BFS/DFS로도 풀 수 있습니다.

최소 경로를 구하는 것이기 때문에 특정 값은 단 한 번만 가야 합니다.

 

$X$에서 $(X-1)$, $(X+1)$, $(2*X)$ 노드로 이동할 수 있으며 이를 트리 형태로 표현하면 다음과 같습니다.

Depth가 1 증가할 때마다 탐색 횟수를 1 증가시키며 K값에 도달할 경우의 탐색 횟수가 정답입니다.

 

전체 코드는 다음과 같습니다.

import sys
from collections import deque

input = sys.stdin.readline

n, k = map(int, input().strip().split(" "))
visited = [[False, 0]] * 100001
queue = deque()

queue.append(n)

# 방문 여부와 탐색 횟수를 저장
visited[n] = [True,0]

if n == k :
    print(0)
    exit()

while queue :
    target = queue.popleft()

    for next in [target-1, target+1, target*2] :
    	# 방문하지 않은 값을 만나면
        if 0 <= next <= 100000 and not visited[next][0] :
            queue.append(next)
            # 부모 노드의 Depth + 1
            visited[next] = [True, visited[target][1] + 1]

            if next == k :
                print(visited[next][1])
                exit()