알고리즘/문제 풀이
[Python/파이썬 13549 백준] 숨바꼭질 3
광규니
2021. 4. 10. 00:32
반응형
www.acmicpc.net/problem/13549
13549번: 숨바꼭질 3
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
풀이
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])반응형