Algorithm
백준
Python
숨바꼭질

숨바꼭질 1697

문제 링크 : https://www.acmicpc.net/problem/1697 (opens in a new tab)

내 풀이

시간 초과로 실패

import heapq
 
N, K = map(int, input().split())
 
pq = [[0,N]]
heapq.heapify(pq)
 
if N == K :
  print(0)
else :
  while pq :
    cnt, val = heapq.heappop(pq)
    cnt += 1
    next = val + 1
    if next == K :
      break
    else :
      heapq.heappush(pq, [cnt, next])
    next = val * 2
    if next == K :
      break
    else :
      heapq.heappush(pq, [cnt, next])
    next = val - 1
    if next == K :
      break
    else :
      heapq.heappush(pq, [cnt, next])
 
  print(cnt)

다른 사람 풀이

dp로 풀어보려고도 하고 deque로도 풀어보려고 했지만 실패해서 다른 사람의 풀이를 봤다.

from collections import deque
 
def bfs() :
  q = deque()
  q.append(n)
  while q :
    x = q.popleft()
    if x == k :
      # 방문한 횟수를 출력한다.
      print(dist[x])
      break
    # 나올 수 있는 경우의 수는 x - 1, x + 1, x * 2 3가지 뿐이다.
    for nx in [x - 1, x + 1, x * 2] :
      if 0 <= nx <= MAX and not dist[nx] :
        # 이전에 방문한 횟수에 1을 더해준다.
        dist[nx] = dist[x] + 1 
        q.append(nx)
MAX = 10 ** 5
dist = [0] * (MAX + 1)
n, k = map(int, input().split())
bfs()

배운 점

  • visited를 적극 활용해서 메모리 낭비를 방지하자!
  • 10 ** 5 와 같이 X의 N 승을 구할 수 있다!