[ baekjoon ] 12851. 숨바꼭질

ayoung0073·2021년 3월 27일
0

baekjoon

목록 보기
57/59
post-thumbnail


문제 링크



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

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

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

profile
백엔드 공부 -ing

0개의 댓글