[Backjoon] 13549 숨바꼭질 3 Python 문제 풀이

출처 : 링크텍스트

문제해석

시간 가중치가 0과 1 둘로 나누어진다.
걷기 : x+1, x-1은 1초가 걸리고
순간이동 : 2*x는 0초가 걸린다.

단계가 이루어진다는 점으로 큐를 2개로 나눠 구현하는 방법이나

양방향 큐인 deque를 활용하여 2개를 별도로 만들지 않고, 순간이동할 경우 맨 앞에 추가, 걷기를 할 경우엔 뒤에 추가한다.

해답코드

#숨바꼭질 3
import sys
from collections import deque

MAX = 100001
isVisited = [False] * MAX
time = [-1] * MAX

input = sys.stdin.readline

n, k = map(int,input().split())
q = deque()
q.append(n)
isVisited[n] = True
time[n]=0

while q:
    now = q.popleft()
    if now == k:
        print(time[k])
        break
    if now-1>=0 and isVisited[now-1]==False: #x-1
        q.append(now-1)
        isVisited[now-1]=True
        time[now-1]=time[now]+1
    if now * 2 < MAX and isVisited[now*2]==False: #순간이동
        q.appendleft(now*2) #순간이동은 0초이므로 최우선순위
        isVisited[now*2] = True
        time[now*2]=time[now] #순간이동은 시간변동 x
    if now+1 < MAX and isVisited[now+1]==False: # x+1 이동
        q.append(now+1)
        isVisited[now+1]=True
        time[now+1] = time[now]+1

주의할 점

• 분명 제대로 풀었다고 생각했는데 계속 99%에서 틀림이 나오길래 내가 대체 어디서 잘못한 걸까 헤매는 시간이 길었다.
• 99%에서 틀린 이유는 처음에 if 조건문의 순서를 +1이 -1보다 앞에 있었다. 해당 경우의 반례로서는 이러한 경우가 있었다.
• input 4 6 output 1
• (4-3-6) 1초
• 만약 +1이 앞에 있으면 2초로 나온다.