[알고리즘/파이썬] 1697번 - 숨바꼭질

 

 

 

 

1697번: 숨바꼭질

 

쉽게 생각하고 갔다가 시간초과와 런타임에 두드려 맞았다.

 

시간 초과는 que에서 pop한 값이 이전에 한번이라도 방문했던 위치라면 이동을 수행하지 않도록 하면 해결된다.

 

런타임에러도 발생했는데 발생할수 있는 숫자의 범위를 제한하지 않아서 발생한 경우였다. ( 출력가능한 숫자 범위를 초과 하면서 에러 발생 )  if 2*x <= 100000 식으로  발생가능한 숫자의 범위를 제한하면서 해결했다.

 

n,k = map(int,input().split())

# BFS를 위한 que
que = []

# 방문 여부를 판단하기위한 que
v_que = [ 0 for _ in range(100001)]

# 방문한 곳의 depth를 기록하기 위한 que
depth = []

# 출발위치 입력.
depth.append(0)
que.append(n)

while True:
	
    # 현재위치와 depth
    x = que.pop(0)
    xc = depth.pop(0)
    
    # 방문하지 않았던 곳이면 실행.
    if v_que[x] != 1 :
        v_que[x] = 1
		
        # 총 3가지 이동옵션이 있음
        # 조건을 만족할시 이동 수행.
        if x-1 >= 0:
            que.append(x-1)
            # 현재 depth + 1
            depth.append(xc + 1)
        if 2*x <= 100000 :
            que.append(2*x)
            depth.append(xc + 1)
        if x+1 <= 100000 :
            que.append(x+1)
            depth.append(xc + 1)

    if x == k:
        print(xc)
        break