[백준] 1697 : 숨바꼭질 python

 

스타트링크 문제와 매우 유사한 문제였다.

100,000을 넘지 않는 범위에서 X+1, X-1, X*2로 이동하는 경우의 이동횟수를 리스트에 저장하면서 BFS 탐색을 해줬다.

 

from collections import deque
n,k = map(int,input().split())

MAX = 100001

def bfs(s,k):
	# 0번째 열에는 방문체크를
    # 첫 번째 열에는 이동하는 데에 걸린 시간을 저장함
    visited =[[0]*2 for i in range(MAX)]
    queue = deque()
    queue.append(s)
    visited[s][0] = 1
    visited[s][1] = 0
    while queue:
    	# 현재위치를 c에 저장함
        c = queue.popleft()
        if c==k:
            print(visited[c][1])
            return
        # c*2, c+1, c-1 중 범위를 벗어나지 않고
        # 아직 방문하지 않은 곳이 있다면
        # 이동 시간을 1 증가시켜서 저장하고 BFS 탐색을 이어서 함
        for i in (c*2, c+1, c-1):
            if 0<=i<MAX and visited[i][0]==0:
                queue.append(i)
                visited[i][0] = 1
                visited[i][1] = visited[c][1]+1
            
bfs(n,k)