[백준] 점프 점프, A->B

문제

[백준] 점프 점프
[백준] A->B

점프 점프

풀이

bfs 풀었을 때, 메모리나 시간초과가 떴다. 그래서 dp(dynamic programming)을 이용했다.
처음부터 살피면서 그 위치가 이전의 값들에 의한 최소값을 가질 수 있도록 만들려 했다.
갖고 있는 값이 x <= idx 이므로 ‘x의 index를 가지고 있는 값들의 dp’와 ‘idx가 갖고있는 dp+1’를 비교해서 작은 값을 가질 수 있도록 했다.

처음엔 dp[0] * (n+1) 을 이용했으나, 이를 이용한다면
4
0 0 5 0
일 때, 1이 나오게 된다.
따라서 가질 수 없는 값을 dp 값의 기본으로 뒀어야 했다.
이것 때문에 오래 걸렸다.

틀린 풀이 (bfs)

from collections import deque
n = int(input())
data = list(map(int, input().split()))

def search(data, idx):

    answer = 0
    q = deque()
    q.append([idx, answer])
    while q:
        
        idx, ans = q.popleft()

        for i in range(1, data[idx]+1):
            if idx + i == n:
                return ans + 1      # 정답 idx일 경우, return
            if i >= n-1:            # 정답 idx를 넘을 경우, break
                break

            q.append([idx + i, ans+1]) # 아니면 collect
    
    return -1

print(search(data, 0))

정답 풀이 (dp)

n = int(input())
data = list(map(int, input().split()))
dp = [n+1] * (n+1)
dp[0] = 0
for now_idx in range(len(data)):
    jump_idx = data[now_idx]

    for ji in range(1, jump_idx+1):
        next_idx = now_idx + ji
        if next_idx >= n:
            break

        dp[next_idx] = min(dp[next_idx], dp[now_idx]+1)

if dp[n-1] == n+1:
    print(-1)
else:
    print(dp[n-1])

A->B

풀이

bfs를 이용해서 모든 탐색을 이용했다.
이때 적절하지 않은 조건은 제외를 시키거나 정답에 도착했을 때 빠르게 return할 수 있도록 했다.

from collections import deque
start, end = map(int, input().split())

def bfs(start, end):

    answer = 1
    x, y = 2*start, int(str(start)+"1")
    if x == end or y == end: # 처음 값 비교
        return answer + 1

    q = deque()
    q.append([x, answer+1])
    q.append([y, answer+1])
    while q:

        n, answer = q.popleft()
        
        x, y = n*2, int(str(n) + "1")
        if x == end or y == end:    # 같으면 return
            return answer + 1
        if x < end:                 # 작을 경우만 넣기
            q.append([x, answer+1])
        if y < end:
            q.append([y, answer+1])

    return -1

print(bfs(start, end))