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

 

문제

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

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

입력

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

출력

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

 

 

 

 

해설:

 

아... 가지치기하다가 숨 막혀 죽을 뻔..

 

이 문제는 BFS와 백트래킹을 이용해서 풀었다.

 

import sys
import collections
import heapq
 
N, K = list(map(int, sys.stdin.readline().split()))
 
stack = collections.deque([N])
 
 
def bfs():
    time = 0
    point = [False] * 100001
    point[N] = True
    while True:
        for _ in range(len(stack)):
            k = stack.popleft()
            if k == K:
                print(time)
                return
            if 2 * k < 1.5 * K and 2 * k <= 100000:
                if point[2 * k] is False:
                    stack.append(2 * k)
                    point[2 * k] = True
            if 0 <= k + 1 <= 100000:
                if point[k + 1] is False:
                    stack.append(k + 1)
                    point[k + 1] = True
            if k - 1 >= 0:
                if point[k - 1] is False:
                    stack.append(k - 1)
                    point[k - 1] = True
        time += 1
 
 
bfs()
 

 

코드 자체는 어렵지 않은데

 

범위를 나눠주는 일이 나한테는 귀찮았다.

 

우선 방문했던 곳을 체크해야 메모리 초과 or 시간 초과가 뜨지 않아서 그리 했고

 

visited = []로 해서 방문한 값을 추가해봤지만

 

visited에 값을 넣고 그 안에 값이 있는지 조회하는 게 너무 오래 걸려서 시간 초과가 뜸;

 

그래서 메모리 차지는 좀 있지만 시간을 적게 잡아먹는 길이가 100001인 리스트를 만들었다.

 

모든 값은 0~100000 사이의 값만 들어가야 하고

 

2*k를 할 때 K 값과 너무 차이가 날 필요는 없으니까 내 뇌피셜로다가 2 * k < 1.5 * K 정도로 설정했음.