[bfs/백준] 1697번 : 숨바꼭질

- 문제 : https://www.acmicpc.net/problem/1697

 

문제 이해 

- 현재 위치(x)에서 동생이 있는 위치에 가는 3가지 방법(x - 1, x + 1, 2 * x)으로 이동한다.

- 이동할 때 1초가 걸리는데, 3가지 방법으로 1초에 칸을 이동하므로 bfs를 이용해서 진행한다. 

- 여기서는 2차 행렬이 아닌 1차 배열인 arr를 이용해서 방문여부 + 걸리는 시간을 저장한다. 

 

풀이 로직

- 최대 숫자가 10만이므로 number를 10만으로 설정한 뒤 배열 arr를 만든다. 시작하는 n은 중복해서 가면 안되므로 arr[n] = 1 처리한다.

- bfs를 진행하는데, 도착한 지점이 k라면 arr[k] - 1을 출력한 뒤 루프를 break 한다.

arr[k] - 1을 하는 이유는 처음에 arr[n] = 1로 시작하지만 시간은 0초이므로 시간과 배열값이 1 차이가 나기 때문이다.

 

정답 풀이 

from collections import deque

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

number = 10 ** 5
arr = [0 for _ in range(number + 1)]
arr[n] = 1
queue = deque()
queue.append(n)
while queue:
    x = queue.popleft()
    if x == k :
        print(arr[x] - 1)
        break
        
    for i in [x - 1, x + 1, 2 * x]:
        nx = i
        if 0 <= nx <= number and arr[nx] == 0:
            arr[nx] = arr[x] + 1
            queue.append(nx)