백준 1697번: 숨바꼭질

https://www.acmicpc.net/problem/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는 정수이다.

출력

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

예제 입력 1 

5 17

예제 출력 1 

4

---

BFS를 이용하는 문제

 

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

dist=[0] * 100001 #dist[x]=처음 n 위치에서 x위치까지 갈 때까지 걸린 최소 초를 저장함. 
# 좌표 최대값이 100000이고, 인덱스를 100000까지 사용할 것이기 때문에 100001짜리 리스트를 생성함

queue=deque()
def bfs():
    queue.append(n)
    while queue:
        x=queue.popleft()
        if x==k: #잡은 경우
            print(dist[x]) #걸린 시간 출력
            break #중단
        for nx in (x-1,x+1,x*2): #못잡은 경우, -1,+1,*2의 위치를 탐색
            if 0<=nx <=100000: #범위를 벗어나는 경우 중단
                continue
            if dist[nx]==0: #nx위치에 처음 도착하는 경우
                dist[nx] = dist[x]+1 #시간 기록
                queue.append(nx)  
bfs()

 

지금까지 토마토문제 같은거 풀땐... 동서남북으로 탐색했다면..

이건 +1, -1, *2 위치를 탐색하는거라 생각하면 될거같음..

탐색하고...해당 위치에..지금까지 걸린 시간초 기록.. (동생을 찾을때까지) 계속계속하면...

그러면 dist에는.. 어느좌표로 갈 때 최소시간이 얼마인지... 좌표좌표마다 다 기록하고.. 기록한 거기서 또 탐색하고~

동생 찾을때까지 계속계속 반복하다가... 찾으면.. dist[x] 보여주면 되겠다.

 

그리고 토마토문제에서 상자를 벗어나는경우 == 이 문제에서 좌표가 10만을 넘어가는경우라고 생각하면 될듯~

 

암튼 난 이해함