BFS - 숨바꼭질 [1697번]

쉬운줄 알았던데 생각보다 마음대로 풀리지 않아서 상당히 애먹었던 문제이다.

 

처음에는 아래와 같이 풀이를 했으나 무한루프에 빠지는 현상을 발견했다. 왜그런건지 궁금한데... 일단 추정상 not in  으로 리스트안에 값을 찾는 로직이 인덱싱하는 것보다 시간복잡도가 더 커서 그런것이라고 생각이 든다.

 

# 수빈의 현재 점 = N, 동생의 점 = K
# 위치가 X일때 걷는다면 1초 후에 X-1, X+1로 이동
# 순간이동인 경우에는 1초 후에 2*X로 이동

from collections import deque
N, K = map(int, input().split())
time = 0
q = deque([(N, time)])
visited = [N]
while q:
    x, t = q.popleft()
    if x == K:
        print(t)
        break
        
    t+=1
    if (0 <= x-1 <= 100000) and (x-1 not in visited):
        q.append([x-1, t])
        visited.append(x-1)
    if (0 <= x+1 <= 100000) and (x+1 not in visited):   
        q.append([x+1, t])
        visited.append(x+1)
    if (0 <= x*2 <= 100000) and (x*2 not in visited):
        q.append([x*2, t]) 
        visited.append(x*2)

 

그래서 다른 사람들의 풀이를 참고해서 풀었는데 일단 visited 부분을 100001 크기의 리스트로 만들고 여기에 시간을 나타내는 값을 넣는 것이다. 이렇게 인덱싱을 했을때 출력 속도는 훨씬 빨랐다.

 

( 한번 나왔던 숫자가 이후에 나올 수  없는 이유는 목표값을 찾기 위한 '최소횟수'를 구해야하기 때문이다.

따라서 visited[x] = 0이면 한번도 나온 적 없는 숫자, 아니면 이미 이전에 등장한 숫자라는 의미가 된다.)

 

# 수빈의 현재 점 = N, 동생의 점 = K
# 위치가 X일때 걷는다면 1초 후에 X-1, X+1로 이동
# 순간이동인 경우에는 1초 후에 2*X로 이동

from collections import deque
N, K = map(int, input().split())
time = 0
q = deque([(N, time)])
visited = [False] * (100001)

while q:
    x, t = q.popleft()
    if x == K:
        print(t)
        break
        
    t+=1
    if (0 <= x-1 <= 100000) and not visited[x-1]:
        q.append([x-1, t])
        visited[x-1] = True
    if (0 <= x+1 <= 100000) and not visited[x+1]:   
        q.append([x+1, t])
        visited[x+1] = True
    if (0 <= x*2 <= 100000) and not visited[x*2]:
        q.append([x*2, t]) 
        visited[x*2] = True