백준 13549 파이썬

문제

숨바꼭질3

백준 13549

풀이

숨바꼭질 2와 비슷하다.
풀이 방법은 같고 결과 값 찾는 과정 말단 부분만 바꿔주었다.

숨바꼭질 2 문제 풀이 보러가기

바꿔준 부분 1

순간이동의 경우에는 시간이 증가하지 않는다. (0초 후에)
따라서 deque의 appendleft() 를 사용하여 순간이동의 경우에는 queue의 가장 앞부분으로 가도록 코드를 수정하였다.

바꿔준 부분 2

최선의 경우 1가지에 대해서만 찾으면 되도록 결과가 나오는 순간 바로 while문 탈출하도록 수정

정답 코드

# 숨바꼭질 3 
# 숨바꼭질 2 
import sys
from collections import deque
input=sys.stdin.readline



N,K=map(int,input().split())


q=deque()
q.appendleft([N,0])# start , cnt 


visited=[0 for _ in range(100001)] 
while len(q)!=0:
    start,cnt=q.popleft()
    visited[start]=1
    
    if start==K:
        print(cnt)
        break
    else:
        # 답이 아닌 경우 
        if start-1>=0 and visited[start-1]==0:
            q.append([start-1,cnt+1])
        if start+1<=100000 and visited[start+1]==0:
            q.append([start+1,cnt+1])
        if start*2<=100000 and visited[start*2]==0:
            q.appendleft([start*2,cnt])

결과 정답