1697 - 해답

숨바꼭질 

 

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 

수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 

수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 

순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

 

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

작성하시오.

 

입력

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

 

출력

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

---

재귀로 풀려고하니깐 아무래도 무한 루프에 빠지게된다.

import sys

N, K = map(int,sys.stdin.readline().split())

def sol(K,cnt):
    print(N)
    if N == K:
        return cnt
    cnt += 1
    if cnt >= max_cnt:
        return max_cnt

    if K % 2:
        return min(sol(K+1,cnt),sol(K-1,cnt))
    else:
        return min(sol(K+1,cnt),sol(K-1,cnt),sol(K//2,cnt))

max_cnt = abs(K-N)
print(sol(K,0))

 

그래서 알고리즘을 보고 BFS로 풀려고 해보았다.

BFS를 하면서 한번 마다 cnt를 증가 시키고 그 수들을 리스트에 넣어서 해보려고 하였지만 시간 초과 발생.

import sys
from collections import deque

N, K = map(int,sys.stdin.readline().split())

visit = [0] * ((K * 2) + 1)

def bfs():
    cnt = 0
    while q:
        ts = q.popleft()
        re_list = []
        cnt += 1
        for t in ts:
            
            visit[t] = 1               
            
            if K in [t-1,t+1,t*2]:
                return cnt
            if t - 1 > 0 and not visit[t]:
                re_list += [t-1]
                visit[t-1] = 1
            if t + 1 < 2*K and not visit[t]:
                re_list += [t+1]
                visit[t+1] = 1
            if t * 2 < 2*K and not visit[t]:
                re_list += [t*2]
                visit[t*2] = 1


        q.append(re_list)
        

if N >= K:
    print(N - K)
else:
    q = deque()
    q.append([N])
    print(bfs())

그래서 찾은 것이 time을 써서 하는 방법

 

import sys
from collections import deque 

def bfs(): 
    q = deque() 
    q.append(N) 
    while q: 
        v = q.popleft() 
        # K에 도착하면 출력
        if v == K: 
            print(time[v]) 
            return 
        # 3 갈래 다 확인
        for next_step in (v-1, v+1, v*2): 
            # 각각이 범위 내에 있고 타임이 0(처음 방문)이라면
            if 0 <= next_step < MAX and not time[next_step]: 
                # 그렇다면 시간이 1증가 시킨다.
                time[next_step] = time[v] + 1 
                q.append(next_step) 
                

N, K = map(int,sys.stdin.readline().split())
# 최대 K의 2배 보다 작을 것이다 곱하기 2이기 때문에
MAX = 2*K
time = [0]*MAX 

# - + * 뿐이기 때문에
# 작은 쪽으로 가는 방법은 - 뿐이다.
if N >= K:
    print(N - K)
else:
    bfs()