백준 점프 점프 11060 파이썬

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

11060번: 점프 점프

 

 

처음 푼 코드 ( 메모리 초과 )

시간 초과도 아니고 메모리 초과가 났다.  메모리 초과를 의심해 볼 부분은 배열이나 큐에 너무 많은 데이터가 들어가는 곳이다.

아래 코드에서는 덱(deque)에 데이터를 넣는 부분을 의심해 볼 만하다고 생각했다.

import sys
from collections import deque

input = sys.stdin.readline

t = int(input())
board = list(map(int, input().split()))

answer = -1
curr_idx = 0
jump = 0
queue = deque()
queue.append((curr_idx, jump))
while queue:
    curr_idx, jump = queue.popleft()
    if curr_idx == len(board) - 1:
        print(jump)
        exit()

    for i in range(1, board[curr_idx] + 1):
        queue.append((curr_idx + i, jump + 1))
print(-1)

queue 에 데이터를 꾸준히 밀어넣고 있는데, 분명 중복되는 데이터도 append 되고 있을 거라 생각했다.

그럼 중복되는 부분을 체크할 로직을 생성하면 된다.

 

 

정답 코드

위에서 추측한대로 중복 데이터가 queue 에 들어가는 것을 방지하도록 if 문을 구현했다.

visited 라는 배열을 생성하여 이미 queue 에 들어간 적이 있는 데이터가, 다시 queue 에 들어가는 일이 없도록 체크했다.

import sys
from collections import deque

input = sys.stdin.readline

t = int(input())
board = list(map(int, input().split()))

curr_idx, jump = 0, 0
queue = deque()
queue.append((curr_idx, jump))
visited = []

while queue:
    curr_idx, jump = queue.popleft()
    if curr_idx == len(board) - 1:
        print(jump)
        exit()

    for i in range(1, board[curr_idx] + 1):
        next_idx = curr_idx + i
        if next_idx not in visited:
            queue.append((next_idx, jump + 1))
            visited.append(next_idx)
print(-1)