숨바꼭질 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 승을 구할 수 있다!