[Python/파이썬 13549 백준] 숨바꼭질 3

www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

풀이

bfs문제입니다.

2*x, x-1, x+1인 경우에서

 

2*x 인 경우 :

순간이동하므로 시간 +0, appendleft해서 가장 우선순위로 설정하여 1000001까지 최단시간 미리 구해줌

 

x-1,x+1인 경우 :

+1씩 더해줌

 

 

풀면서 시간초과 났었는데

apppendleft를 안써주고 if문으로 하나하나씩 정의해줘서 시간초과났음...

 

import sys
from collections import deque
input=sys.stdin.readline
start,end=map(int,input().split())
graph=[-1]*100001

def bfs(start,end):
    graph[start]=0
    queue=deque()
    queue.append(start)
    while queue:
        x=queue.popleft()
        # 순간이동을 먼저 고려하게돼서 x가 나오면 그만 돌게함
        if x==end:
            return
        for nx in (2*x,x-1,x+1):
            if 0<=nx<100001:
                if graph[nx]==-1:
                    # 순간이동 하는 경우를 우선으로 해서 시간을 최대한 줄임
                    if nx==2*x:
                        graph[nx]=graph[x]
                        queue.appendleft(nx)
                    else:
                        graph[nx]=graph[x]+1
                        queue.append(nx)
            
            
bfs(start,end)
print(graph[end])