[BOJ] 12851. 숨바꼭질

---

문제 링크

---

import sys
from collections import deque
input = sys.stdin.readline

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

q = deque()

q.append((0, n))
ans = int(1e9)
ans_cnt = 0
dp = [int(1e9)] * 100001
while q:
  cnt, now = q.popleft()

  if now == k:
    if ans == int(1e9):
      ans = cnt
      ans_cnt += 1
    elif cnt == ans:
      ans_cnt += 1
    continue

  if cnt > ans:
    break

  else:
    if now - 1 >= 0 and cnt + 1 <= dp[now - 1]:
      q.append((cnt + 1, now - 1))
      dp[now - 1] = cnt + 1
    if now + 1 <= 100000 and cnt + 1 <= dp[now + 1]:
      q.append((cnt + 1, now + 1))
      dp[now + 1] = cnt + 1
    if now * 2 <= 100000 and cnt + 1 <= dp[now * 2]:
      q.append((cnt + 1, now * 2))
      dp[now * 2] = cnt + 1

print(ans)
print(ans_cnt)

BFS 알고리즘을 이용한 문제
배열을 이용해 해당 인덱스(위치)에 시간을 저장한다.
빠른 시간이 나오면 해당 값을 갱신시킨다.

그래서 먼저 배열 값을 10억으로 초기화해놓는다.
그 후 먼저 수빈이가 0초일 때, n의 위치에 있기 때문에 큐에 (0, n)을 넣는다.

큐에서 pop을 했을 때 해당 위치가 k인 경우, 다시 if문을 이용해 문제를 푼다.

---

초반에 heapq를 이용해서 풀다가, 시간초과가 발생했다.

## 12851. 숨바꼭질2

import sys
import heapq
input = sys.stdin.readline

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

arr = []

heapq.heappush(arr, (0, n))
ans = int(1e9)
ans_cnt = 0
while arr:
  cnt, now = heapq.heappop(arr)
  # print(cnt, now)

  if now == k:
    if ans == int(1e9):
      ans = cnt
      ans_cnt += 1
    elif cnt == ans:
      ans_cnt += 1
    continue

  if cnt >= ans:
    break

  else:
    if now - 1 >= 0:
      heapq.heappush(arr, (cnt + 1, now - 1))
    if now + 1 <= 100000:
      heapq.heappush(arr, (cnt + 1, now + 1))
    if now * 2 <= 100000:
      heapq.heappush(arr, (cnt + 1, now * 2))

print(ans)
print(ans_cnt)

아무래도 배열이 있다면 바로 배열 인덱스로 값에 접근할 수 있기 때문에 시간초과가 발생하지 않는 듯하다.

---

21.04.07 복습

## 12851. 숨바꼭질
import heapq
n, k = map(int, input().split())

INF = int(1e9)
dp = [INF for _ in range(100001)]

q = []

heapq.heappush(q, (0, n))
ans = INF
cnt = 0
while q:
  sec, now = heapq.heappop(q)
  
  if sec > ans:
    break
    
  if now == k:
    if ans == INF:
      ans = sec
      cnt += 1
    elif ans == sec:
      cnt += 1
    else:
      break

  
  if now - 1 >= 0 and dp[now - 1] >= sec + 1:
    dp[now - 1] = sec + 1
    heapq.heappush(q, (sec + 1, now - 1))
  if now + 1 <= 100000 and dp[now + 1] >= sec + 1:
    dp[now + 1] = sec + 1
    heapq.heappush(q, (sec + 1, now + 1))
  if now * 2 <= 100000 and dp[now * 2] >= sec + 1:
    dp[now * 2] = sec + 1
    heapq.heappush(q, (sec + 1, now * 2))

print(ans)
print(cnt)

이번엔 dp와 heapq를 이용.

  if now == k:
    if ans == INF:
      ans = sec
      cnt += 1
    elif ans == sec:
      cnt += 1
    else:
      break

처음에 이 조건문을 잘못 써서 78%에서 실패했다.

  if now == k:
    if ans == INF:
      ans = dp[now] 
      cnt += 1
    elif dp[now] == sec:
      cnt += 1
    else:
      break

dp[now]와 sec은 항상 같은 값이다.
ans를 써야하는데 dp[now]로 쓰는 바람에,,

또한

  if sec > ans:
    break

이 조건이 없어도 성공하지만

사진에서 볼 수 있듯이 시간을 훨씬 단축할 수 있다!

---

21.06.29 복습

import sys  
import heapq

input = sys.stdin.readline

n, k = map(int, input().split())
q = []
heapq.heappush(q, (0, n))
INF = int(1e9)
dp = [INF for _ in range(100001)]
min_cnt = INF
answer_cnt = 0

while q: 
  cnt, n = heapq.heappop(q)

  if n == k:
    if min_cnt == INF:
      min_cnt = cnt
      answer_cnt = 1
    elif cnt == min_cnt:
      answer_cnt += 1
    else:
      break

  if n - 1 >= 0 and dp[n - 1] >= cnt + 1:
    dp[n - 1] = cnt + 1
    heapq.heappush(q, (cnt + 1, n - 1))

  if n + 1 <= 100000 and dp[n + 1] >= cnt + 1:
    dp[n + 1] = cnt + 1
    heapq.heappush(q, (cnt + 1, n + 1))

  if n * 2 <= 100000 and dp[n * 2] >= cnt + 1:
    dp[n * 2] = cnt + 1
    heapq.heappush(q, (cnt + 1, n * 2))

print(min_cnt)
print(answer_cnt)

시간초과 파티 ...