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

문제

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

---

문제 요약

수빈이의 위치가 N이고, 동생의 위치가 K일 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 출력한다.

 

수빈이는 걷거나 순간이동을 할 수 있다.

 

수빈의 위치가 X일 때 걷는다면 1초 후에 N-1 또는 N+1로 이동하고, 순간이동을 하는 경우에는 1초 후에 2 × N 위치로 이동하게 된다.

---

코드

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

    min_tm[N] = 0

    while que:
        num = que.popleft()

        if num == K: # K 위치에 도착하면
            break # 종료

        arr = [num + 1, num - 1, num * 2] # 이동할 수 있는 세 가지 경우의 수

        for nx in arr:
            if 0 <= nx < 200000 and min_tm[nx] == -1:
            # nx가 인덱스를 벗어나지 않고, 방문하지 않았다면
                min_tm[nx] = min_tm[num] + 1
                que.append(nx)

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

min_tm = [-1] * 200000
# i 위치로 이동하는데 필요한 최소 시간을 저장하는 배열 (초기: -1)

bfs()

print(min_tm[K])

---

코드 설명

1. i 위치로 이동하는데 필요한 최소 시간을 저장하는 배열 min_tm을 생성한다.

+ 초기 값은 -1이다. (방문하지 않음을 나타냄)

 

2. BFS 탐색을 진행하며 동생이 있는 K 위치에 도착했다면 탐색을 종료하고 min_tm[K]를 출력한다.