숨바꼭질

출처 : 백준 #1697

시간 제한	메모리 제한
2초	128 MB

---

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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

---

예제 힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

---

풀이

풀이 설명

• BFS : python 자료구조인 Deque을 이용하였다.

• 우선 level(=depth) 마다 구분이 필요했다. 따라서 temp에 level 0 에 해당하는 start를 넣은 뒤 그 temp 자체를 queue에 넣어주었다.

• level이 1씩 증가할 때마다, count를 1씩 증가시킴으로써 횟수를 계산 하였다.

• 이런 식으로 temp로써 level을 구분하였고 queue에서 뺀 리스트는 arr로 정하여 arr 내의 원소가 dest(목적지)와 같으면 count를 반환하였다.

이 문제를 풀며 느낀점

• 문제에서 주어진 범위에 집중하자.
• BFS 문제를 풀 때 어떻게 하면 경우의 수를 더 줄일 수 있을지 고민하자.

python code(BFS)

# 백준 1697번
import sys
from collections import deque

def solution(start, dest):
    queue = deque()
    temp = [start]
    queue.append(temp)
    visited = [False] * (10**5+1)
    visited[start] = True
    count = 0
    while queue:
        arr = queue.popleft()
        temp = []
        for x in arr:
            if x == dest:
                return count
            if x - 1 >= 0:
                if visited[x-1] == False:
                    visited[x-1] = True
                    temp.append(x-1)
            if x != 0 and x*2 <= 10**5:
                if visited[x*2] == False:
                    visited[x*2] = True
                    temp.append(x*2)
            if x <= dest:
                if visited[x+1] == False:
                    visited[x+1] = True
                    temp.append(x+1)
        queue.append(temp)
        count += 1


n, k = map(int, sys.stdin.readline().split())
print(solution(n, k))