백준 1697: 숨바꼭질 - 파이썬

숨바꼭질   성공다국어

1697번: 숨바꼭질

문제

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

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

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

내 코드

 

import sys
from collections import deque

def bfs(start):
    que=deque()
    que.append(start)

    while que:
        x=que.popleft()

        if x==b: #목적지에 도달했으면 stop하고 그 좌표의 값 return.
            return count[x]
        
        for nx in [x-1,x+1,2*x]:
            if nx<0 or nx>limit-1: #좌표 범위 밖이면 불가.
                continue
            if count[nx]!=0: #방문한적 있으면 continue
                continue
            count[nx]=count[x]+1 #이동 전 놈의 값+1로 초기화.
            que.append(nx)


#메인 코드 부분
a,b=map(int,sys.stdin.readline().split())

#a=0, b=10^5일때 최대 10^5까지 이동할 수 있으므로 
#인덱스를 10^5까지 확보하기 위함.
limit=(10**5)+1 

count=[]
for _ in range(limit): #count인덱스는 0~limit-1 까지 가능
    count.append(0) #값이 0이라는 뜻 = 아직 방문 X

print(bfs(a))

 

풀이 및 접근)

- 미로에서 최단거리 찾는 문제와 비슷하다고 생각했다. 다만 조건에서 이동거리가 달랐으므로 이를 반영하면 되는 문제이다.

- for nx in [x-1, x+1, 2*x]에서 이동 가능한 거리를 선택할 수 있게 한다.

- 포인트는, count[?] 값이 0이면 아직 방문하지 않았다는 뜻이고, 0이 아닌 값이 있으면 방문하여서 그 값을 건들지 말아야 하는 값이다. 아직 방문하지 않았다면 이동하기 전의 값에 1을 더한 값으로 초기화 한다.

- 이 문제에서 또 중요한 점은, 인덱스의 범위를 정확하게 가져가는 것이다. 출발: 0 도착:100000일때, 최대 이동 거리는 걸어서만 가는 100000일 것이다. 그러면 100000으로 인덱스 접근이 가능해야 하므로 count의 원소 개수를 100000+1개로 한 것이다. 100000+1번째 값이 count[100000]이 될테니 말이다.

- 위를 잘 적용하지 않으면 런타임 에러가 발생한다.