메모리를 아껴보자

#13913번 숨바꼭질4 https://www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

이 전에 풀었던 숨바꼭질 문제(https://www.acmicpc.net/problem/1697)에서

단순히 거리만을 저장하는게 아니라 경로를 저장하는 형태로 코드를 변경했다.

N, T = map(int, input().split())
M = 10**5

dist = [[]]*(M+1)
dist[N] = [N]


def solve(position):
    que = []
    que.append(position)

    while que:
        p = que.pop(0)
        if p == T:
            print(len(dist[p])-1)
            for i in dist[p]:
                print(i, end=" ")
            return dist[p]

        for np in [p-1, p+1, p*2]:
            if 0 <= np <= M and not dist[np]:
                dist[np] = dist[p] + [np]
                que.append(np)


solve(N)

결과는 메모리 초과.

그럴만도하다... 10**5개의 리스트에 리스트를 저장하는 형태니까..

 

그래서 백준 질문을 뒤져보았고 대안을 얻었다.

2진수를 사용하는 방법도 있다고 하지만 번거로워보여서 패스

딕셔너리를 이용하는 방법을 선택했다.

N, T = map(int, input().split())
M = 10**5

dist = {}
def solve(position):
    que = []
    que.append(position)

    while que:
        p = que.pop(0)
        if p == T:
            return p

        for np in [p-1, p+1, p*2]:
            if 0 <= np <= M and np not in dist.keys():
                dist[np] = p
                que.append(np)

last = solve(N)
answer = []
while last != N:
    answer.append(last)
    last = dist[last]
answer.append(last)

print(len(answer)-1)
print(" ".join(map(str, answer[::-1])))

이전 위치만 기록하는 형태이다.

45 : 43 형태로 저장된다면 45로 가기 전 위치는 43이라는 뜻이다.

 

굉장히 현명한 방법이라고 생각했다.

저런 생각 하는 사람들이 플레티넘 가는거구나...