[백준] 1697. 숨바꼭질 (Python)

📌 1697. 숨바꼭질

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

풀이과정

1. DP

n, m = map(int, input().split())

INF = int(1e9)
dp = [INF]*(max(n,m)+1)

dp[n] = 0

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

print(dp[m])

처음에는 가장 빠른 시간을 구해야한다는 것을 보고 다이나믹 프로그래밍을 생각해서 코드를 짰다. 하지만 짜다보니 문제가 발생하는 것을 알게 되었다. 이 문제는 -1으로도 갈 수 있어서 다시 돌아오는 과정이 dp로는 잘 되지 않는다.

2. BFS

from collections import deque

n, m = map(int, input().split())

def check(a):
  if a>=0 and a<=100000:
    return True
  else:
    return False

distance = [0]*(100001)
q = deque()
q.append(n)

while q:
  now = q.popleft()
  if check(now+1) and distance[now+1] == 0:
    q.append(now+1)
    distance[now+1] = distance[now] + 1
  if check(now-1)and distance[now-1] == 0:
    q.append(now-1)
    distance[now-1] = distance[now] + 1
  if check(now*2) and distance[now*2] == 0:
    q.append(now*2)
    distance[now*2] = distance[now] + 1

if n == m:
  print(0)
else:
  print(distance[m])

그렇다. BFS로 가능한 문제였다. 수빈이의 위치를 시작점으로 -1, +1, *2를 해주고 나온 결과 값을 또 반복해서 -1, +1, *2 해주면 최소 시간이 나오게 될 것이다. 주의해야할 점은 범위를 100001로 지정해야 한다는 것이다. 돌아오는 과정에서 최소 시간이 나올 수 있기 때문이다.

💯 정답

from collections import deque

n, m = map(int, input().split())

def check(a):
 if a>=0 and a<=100000:
   return True
 else:
   return False

distance = [0]*(100001)
q = deque()
q.append(n)

while q:
 now = q.popleft()
 if check(now+1) and distance[now+1] == 0:
   q.append(now+1)
   distance[now+1] = distance[now] + 1
 if check(now-1)and distance[now-1] == 0:
   q.append(now-1)
   distance[now-1] = distance[now] + 1
 if check(now*2) and distance[now*2] == 0:
   q.append(now*2)
   distance[now*2] = distance[now] + 1

if n == m:
 print(0)
else:
 print(distance[m])