[알고리즘 일기 - 파이썬] 169. 숨바꼭질

문제 169. (2022-01-30)

 

1697번: 숨바꼭질

Baekjoon 1697. 숨바꼭질

[파이썬(python) 풀이]

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

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

---

입력

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

---

출력

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

---

입력 예시

5 17

---

출력 예시

4

---

❧ 정답

 

 

👉 수빈이가 방문한 모든 점들에 대한 소요 시간을 계산한다.
👉 만약 수빈이가 동생을 찾았다면 탐색을 멈추고 해당 좌표에 도달하기 까지의 시간을 출력한 뒤 프로그램을 종료한다.

 

💡 dfs & bfs 풀이방법을 생각하기가 쉽지 않다.
🌟 처음 방문 위치로 부터 규칙적으로(v - 1, -> v + 1 -> v * 2) 이어지며 방문하고 시간을 저장하므로 dfs & bfs 풀이를 생각할 수 있다!

 

💡 for 문의 방문 순서를 반드시 v - 1, v + 1, v * 2 순으로 해야한다!
∵ 맨 처음 초기화를 '0'으로 했기때문!
만약 v * 2, v + 1, v - 1 순으로 방문을 진행한다면 (0, 0)좌표 경우 time[0] = 1이 되고, time[1] = 2가 된다.
이렇게 되면 실제 값과 비교했을때 오차가 발생한다! (원래 값 : time[1] = time[0](=0) + 1 = 1 )

- 참고 URL

글 읽기 - 두개의 코드의 차이를 모르겠습니다.

 

❧ 오답 제출 코드

from sys import stdin
from collections import deque

n, k = map(int, stdin.readline().split())
if n == k:
    print(0)
    exit(0)

time = [0] * (k * 2)
time += [0]


def bfs(v):
    queue = deque([v])
    while queue:
        v = queue.popleft()
        for nv in (v - 1, v + 1, v * 2):
            if nv < 0 or nv > (k * 2) or time[nv]:
                continue
            time[nv] = time[v] + 1
            queue.append(nv)


bfs(n)
print(time[k])

• 수빈이가 동생을 찾으러가는 경로에서 방문하는 점의 좌표 최댓값을 k * 2로 생각했다.
  • 수빈이가 있을 수 있는 좌표 최댓값을 k로 생각해서 이에 * 2한 값을 최대값으로 생각
  • 그러나, 수빈이가 동생보다 멀리 있을 수 있다는 사실을 간과함 -> 범위 다르게 책정

 

🌟 예외 케이스를 고려하며 코드를 짜야한다. (기본적으로 최소, 최대 값을 포함하는 경우를 테스트 케이스로 적용하며 점검해보기)