1697번 : 숨바꼭질

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

 

아이디어

1. 기존 BFS 그래프 탐색을 X-1, X+1, 2*X로 대체한다

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

import sys
from collections import deque

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

def BFS(N, K) :
    visited = [-1 for _ in range(100001)]
    q = deque([N])
    visited[N] = 0
    
    while q :
        u = q.popleft()
        if u == K :
            print(visited[u])
            break
        
        # search
        v1 = u + 1
        if v1 <= 100000 and v1 >= 0 and visited[v1] == -1 :
            q.append(v1)
            visited[v1] = visited[u] + 1
        v2 = u - 1
        if v2 <= 100000 and v2 >= 0 and visited[v2] == -1 :
            q.append(v2)
            visited[v2] = visited[u] + 1
        v3 = 2 * u
        if v3 <= 100000 and v3 >= 0 and visited[v3] == -1 :
            q.append(v3)
            visited[v3] = visited[u] + 1
        
BFS(N, K)

 

헤멨던 점

• 메모리 초과 문제
• 계속 코드를 짜왔던 것처럼, BFS 탐색 수를 defaultdict에 튜플 형식으로 저장했는데 이 부분이 메모리 초과 문제를 초래했다
• 이를 해결하기 위해 visited에 탐색 횟수를 기록하도록 했다.