백준 13913 숨바꼭질4

 

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

 

 

숨바꼭질3에서 경로를 출력해야하는 문제다.경로를 출력하는 방법은 여러가지가 있다.

​

1. que에 경로를 함께 기억한다.
2. 경로 배열을 만들고, 각 배열에 올 수 있는 가장 빠른 경로를 업데이트 한다

이렇게 할 경우, 2번은 메모리 초과가 발생했다. 따라서 1번 방법으로 접근했다.

​

1번 방법으로 접근했을 때, 모든 경로를 숫자로 직접 입력해두었을 때 간단한 연산임에도 불구하고 어마어마한 시간이 필요했다. 돌이켜보면 10만개를 다 돌릴 수도 있는데, 10만개에 대한 주소를 모두 Path로 가지고 있다면 그 String을 넘겨주는 것과 메모리는 장난이 아닐꺼다.

​

"100000 99999 99998 ... 1... 이렇게 온다고 생각해보면 말이다. " 문자열이 어마어마하게기니 문자열 덧셈을 할 때 어마어마한 시간이 걸릴 수 밖에 없다. 물론 저렇게 하더라도 통과는 되지만 0.6초나 소요된다.

​

5개월 전에 나는 500ms에 풀었는데, 이번에는 6000ms가 걸렸다. 위 문자열을 좀 더 줄이는 방법을 고민해봤는데, 결국은 +, -, *만 잘 남겨두면 된다. 그리고 마지막 좌표를 기준으로 +,-,* 현재의 위치를 표현하고 마지막에 일괄적으로 출력할 수 있다.

​

​

import sys
from collections import deque

def sol(n,k):
    que = deque()
    que.append((n,0,""))
    v[n] = 0

    while que :
        now_posi, time, path = que.popleft()

        if now_posi == k :
            print(time)
            return path

        next_time = time + 1

        if now_posi + 1 <= 100000 and v[now_posi + 1] > next_time :
            v[now_posi + 1] = next_time
            que.append((now_posi + 1 , next_time, path + "+"))

        if now_posi - 1 >= 0 and v[now_posi -1] > next_time :
            v[now_posi - 1] = next_time
            que.append((now_posi -1 , next_time,  path + "-"))

        if now_posi * 2  <= 100000 and v[now_posi * 2] > next_time :
            v[now_posi * 2 ] = next_time
            que.append((now_posi * 2  , next_time, path + "*"))


n,k = map(int,sys.stdin.readline().split())
v = [9876543210 for _ in range(100000 + 1 )]

if n == k :
    print(0)
    print(n)
else :
    myStr = sol(n, k)
    my_list = [n]
    for s in myStr:
        if s == "+":
            my_list.append(my_list[-1] + 1)
        elif s == "-":
            my_list.append(my_list[-1] - 1 )
        elif s == "*":
            my_list.append(my_list[-1] * 2 )

    print(" ".join(map(str, my_list)))