[백준|파이썬] 1697: 숨바꼭질 (실버1)

문제

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

 

🐍파이썬

import sys
from collections import deque
 
n, k = map(int, sys.stdin.readline().split())
#문제에서 주어진 n, k 값의 범위를 활용해 방문여부를 저장하는 리스트를 생성
sumba = [0 for _ in range(100001)]	
 
def bfs(x):
    queue = deque([x])
    while queue:
        x = queue.popleft()
        #x와 k가 동일하면 현재 sumba의 값을 리턴
        if x == k:
            return sumba[x]
        for nx in (x-1, x+1, 2*x):
            if nx < 0 or nx >= 100001:	#인덱스 범위를 넘어서면 건너뛰기
                continue
            if sumba[nx] == 0:	#아직 방문하지 않은 좌표라면
                sumba[nx] = sumba[x] + 1	#방문처리+경로이동횟수 저장
                queue.append(nx)	#다음 방문할 좌표 설정 위해 큐에 nx 삽입
print(bfs(n))	#n에서부터 bfs 시작

 if nx < 0 or nx >= 100001: continue

이 부분 인덱스 처리 때문에 시간이 많이 걸렸다. 인덱스 처리 주의!