[백준]1697 숨바꼭질

1. 풀이

bfs로 풀어야 한다

Q.

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

2. 소스코드

import queue

N,K=map(int,input().split())

q=queue.Queue()
time=0
q.put(N)
visitedL=[0]*100001
visitedL[N]=1

while(q):
    temp=q.get()
    if temp==K:
        print(visitedL[temp]-1) # 수빈이의 첫위치가 0이아니라 1이므로 최종답에 1을 빼야한다.
        break

    a = temp + 1
    if a<=100000 and visitedL[a]==0 :
        visitedL[a]=visitedL[temp]+1
        q.put(a)
    b=temp-1
    if b>=0 and visitedL[b]==0 :
        visitedL[b]=visitedL[temp]+1
        q.put(b)

    c=temp*2
    if c<=100000 and visitedL[c]==0 :
        visitedL[c]=visitedL[temp]+1
        q.put(c)

 

3. 시간을 줄이기 위한 전략

(1) visitedL을 빈 리스트로 시작하여 방문한 위치를 추가하는 방식은 시간이 오래걸린다.

따라서 visitedL을 10만개 초기화하여 인덱스로 접근한다

​

(2) visitedL에 걸린 시간을 점화식으로 표현한다. 이전에 방문했던 위치에서 1씩 더해지는 형태로

*시작위치가 0초이지만 방문되었다는 것을 표현하기 위해 1로 시작한다. 따라서 모든 방문지들이 정답보다 1씩 더해지기 때문에 최종답에선 1을 빼줘야 한다