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

📌 12851. 숨바꼭질 2

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

풀이과정

처음에는 직관적으로 풀었다. 큐에 n을 넣고 +1, -1, *2를 해주면서 k와 같아질 때를 찾고, 그 같을 때의 횟수와 같은 경우를 탐색하고 횟수가 하나 더 커지면 반복문을 나오도록 구현했다.

from collections import deque

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

q = deque()
q.append((0, n))

answer = -1
number = 0
r = int(1e9)

while q:
  sec, now = q.popleft()
  #print(now)
  if now == k:
    answer = sec
    number += 1
    r = sec
  if sec > r:
    break
  
  q.append((sec+1, now+1))
  q.append((sec+1, now-1))
  q.append((sec+1, now*2))

print(answer)
print(number)

하지만 이것도 12919. A와 B 2 문제와 마찬가지로 매번 3가지의 경우의 수가 있기 때문에 3승으로 발산한다. 따라서 시간초과가 발생한다.

이를 해결하기 위해서 visited 배열을 이용해준다. visited[n][0]에는 n이 되기 위한 최소 횟수, visited[n][1]에는 최소 횟수가 되는 경우의 수를 담는다. 이 visited를 계산할 때 약간 dp느낌이 나는 듯하다. 이전의 것을 참고하여 현재의 계산에 넣기 때문이다. 그래서 난이도가 더 높게 느껴진 듯 하다.

💯 정답

from collections import deque

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

q = deque()
q.append(n)

visited = [[-1]*2 for _ in range(100001)]
visited[n][0] = 0
visited[n][1] = 1

while q:
  now = q.popleft()
  for i in [now-1, now+1, now*2]:
    if 0<= i <= 100000:
      if visited[i][0] == -1: # 처음이라면
        visited[i][0] = visited[now][0] + 1
        visited[i][1] = visited[now][1]
        q.append(i)
      elif visited[i][0] == visited[now][0] + 1: # 최소 횟수와 횟수가 같다면
        visited[i][1] += visited[now][1]

print(visited[k][0])
print(visited[k][1])