[백준 13913번] 숨바꼭질4 - python

문제링크

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

13913번: 숨바꼭질 4

 

풀이 

- 처음에는 큐에 route라는 배열도 함께 넣어줘서 위치 이동할 때마다 route 배열에 경로 추가해주는 방식으로 구현하였는데

메모리 초과 발생 

내가 구현한 것처럼 경로를 모두 다 기록하게 되면 O(n^2)의 메모리가 필요하게 되어 메모리 초과가 발생한다고 한다.

따라서 모든 경로는 저장하는 것이 아니라, 자취를 남기는 식으로 구현해야했다. 

path 배열에 자취를 남겼는데

path[a] = b 는 b에서 a로 왔음을 의미한다.

따라서 k에 도착했을 때 path배열을 거꾸로 읽어가면 경로를 알 수 있게 된다. 

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

def bfs(n,k):
    
    q = deque()
    # 방문표시 
    visited = [False] * 100001
    visited[n] = True
    # 자취를 저장할 배열 
    path =[0] * 100001
    # 출발지 표시 
    path[n] = n
    # 위치, 이동 횟수 
    q.append((n,0))

    while q:
        now, cnt = q.popleft()
    
   		# k에 도착했다면 
        if now == k :
            print(cnt)
     		# 경로를 기록할 배열 
            answer = []
            x = now
            answer.append(x)
            # 출발지에 도착하기 전까지 
            while path[x] != x :
            	# 경로 읽기 
                answer.append(path[x])
                x = path[x]
            # 거꾸로 저장되어있으므로 
            answer.reverse()
            # 출력 
            print(*answer)
            return answer 
            
        # 범위에 속하고 방문하지 않았으면 
        if now + 1 < 100001 and not visited[now+1] :
        	#자취 표시
            path[now+1] = now
            # 큐에 삽입 
            q.append((now+1, cnt +1 ))
            # 방문 표시 
            visited[now+1] = True
            
        # 범위에 속하고 방문하지 않았으면 
        if 0 <= now - 1 < 100001 and not visited[now-1]:
            path[now-1] = now
            q.append((now-1, cnt +1))
            visited[now-1] = True
        
        # 범위에 속하고 방문하지 않았으면     
        if now * 2 < 100001  and not visited[now*2] :
            path[now*2] = now 
            q.append((now*2, cnt +1))
            visited[now*2] = True
            
    return -1 
    
n, k = map(int,input().split())
bfs(n,k)