boj1697 - 숨바꼭질

문제

https://www.acmicpc.net/problem/1697

코드 (816ms)

import sys
input = sys.stdin.readline
from collections import deque

N, K = map(int, input().split())
visited = [False for _ in range(100000+1)]

if N == K:
    print(0)
else:
    q = deque()
    q.append((N,0))
    while q:
        n, s = q.popleft()
        visited[n] = True
        for i in [1,-1,n]:
            tn = n+i
            if 0<=tn<=100000 and not visited[tn]:
                q.append((tn,s+1))
            if tn == K:
                print(s+1)
                sys.exit()

코드 - 메모리초과

import sys
input = sys.stdin.readline
from collections import deque

N, K = map(int, input().split())
    
if N == K:
    print(0)
else:
    q = deque()
    q.append((N,0))
    while q:
        n, s = q.popleft()
        for i in [1,-1,n]:
            tn = n+i
            if 0<=tn<=max(N,K):
                q.append((tn,s+1))
            if tn == K:
                print(s+1)
                sys.exit()
               

설명

bfs 문제 - 수빈이가 이동가능한 방법을 step으로 두고 BFS
메모리 초과 코드는 visit처리를 안해줘서 방문한곳 또 방문한게 원인!

다른 사람 코드 (68ms)

def tri_validation(N, K):
  if N >= K:
    return N - K
  elif K == 1:
    return 1
  elif K % 2 != 0:
    return 1 + min(tri_validation(N, K - 1), tri_validation(N, K + 1))  
  elif K % 2 == 0:
    return min(K - N, 1 + tri_validation(N, K // 2))

N, K = map(int, input().split())

answer = tri_validation(N, K)

print(answer)

설명

수빈이가 순간이동으로 이동할 수 있는 경우는 2*N이므로 K>N 이어야 최단거리.
N>K라면 수빈이는 -1로 이동하며 동생에게 가는 것이 최단거리이다.
따라서 첫번째 if 문에서 N>=K인 경우 N-K return

두번째 if 문 부터는 N<K 이다.
N<K 이고 k==1 인 경우는 N=0, K=1인 경우뿐이니 1 return

세번째 if문은 K가 홀수인 경우, k-1과 k+1은 짝수이고 순간이동 이용시 빠르게 도착가능하기 때문에 둘 중 더 작은 거리에서 1을 더해서 return

네번째 if문은 K가 짝수인 경우, N이 K의 약수가 아닌 경우와 약수인 경우 중 최단거리 return

• 코드출처 : vim_hjk님 코드