[백준 1697] 숨바꼭질 [Python]

백준 - 1697

---

풀이

수빈이가 동생한테 가는 방법은 현 위치(N)에 대해 3개의 방법(N + 1, N - 1, 2N)이 있다.

항상 N이 K에 가까워지는 방법이 정답이라는 보장이 없기 때문에 모든 경우에 대해 탐색을 해봐야 한다.

Queue에 수빈이의 범위 내의 새로운 위치를 담아주고, 다시 꺼낼 때 이동 횟수를 기록한다.

단, 이미 방문한 위치를 재 방문할 때는 이동횟수가 같거나 크기 때문에 최소 이동횟수 기록을 보장하기 위해 방문하지 않은 경우에만 Queue에 담아두었다.

 

Queue의 변화에 대해 궁금하다면 아래를 참고하자.

처음에 주어진 N(5)에 대한 3가지 이동 방법을 모두 기록하며, Queue에서 새로운 위치(nx)를 꺼낼때마다 이에 대한 이동 방법 또한 기록한다.

빨간색 대각선은 동일한 이동시간을 가진 위치가 어디까지 인지를 나타낸 것이다.

첫 번째 대각선의 10까지는 1회,

두 번째 대각선의 20까지는 2회, ...

계속 반복하다 꺼낸 nx가 K와 동일할 때, 이동시간인 time[nx]을 반환하는 방식으로 풀이했다.

---

소스코드

소스코드 보기

---

출처

1697번: 숨바꼭질