백준 11060 : 점프 점프

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

11060번: 점프 점프

https://github.com/HPYoo/swcodingtest/blob/main/prob11060.py

GitHub - HPYoo/swcodingtest: 코딩테스트 대비 연습

다이나믹 프로그래밍으로 푸는 경우가 많은데, 아직 공부가 덜되서 BFS로 해결.

모든 경로에 대해 탐색을 하니 메모리 초과, deque를 안쓰니까 시간초과로 많이 애먹었던 문제.

또한, 지도가 1X1인 경우도 고려해야 한다. 

 

예외적인 상황, 시간, 메모리 세 가지 요소를 고려안하고 자만하면 바로 함정에 빠져버리는 문제인 것 같다.

 

1. 방문처리 활용

 방문처리 배열을 사용하지 않으면 BFS 특성상 메모리 초과에 걸릴 수 밖에 없었다.

따라서, 한 번이라도 방문한 경우 재방문하지 않도록 해주어야 한다. 예를 들어, 기본 예제에서 5번 위치에 있는 상황을 고려해보자.

 

5번 위치에서 점프가 가능한 경우는 3가지다. 따라서 큐에는 3가지 경우에 대한 정보가 들어가게 된다. 여기에서 우리는 8번 위치에서 다시 점프를 하는 경우가 최소의 경우라는 것을 직관적으로 알고 있다. 6번과 7번에 도달한 경우에는 8번 위치에서 다시 시작한 경우보다 한 번 더 뛰는 셈이 되는 것이기 때문에 고려할 필요가 없다. 따라서, 이미 방문한 곳에는 다시 방문할 필요가 없으므로, 방문처리 배열을 만들어서 방문하지 않은 경우에만 큐에 넣어서 갱신을 시켜주면 된다. (해당 부분 다시 정리하면서 말을 정리해보자)

 

2. 전체 코드

메모리 116188 KB 시간 176 ms

복습을 철저히 하자.

from collections import deque
N = int(input())
step = list(map(int, input().split()))

def bfs():
    minValue = 101
    if len(step) == 1 :
        return 0
    q = deque()
    q.append([1, step[0], 0])
    visited = [False for _ in range(N+1)]
    visited[1] = True
    while q :
        loc_x, x, cnt = q.popleft()
        sign = False
        for i in range(1, x + 1):
            loc_nx = loc_x + i
            if loc_nx < N and not visited[loc_nx]:
                visited[loc_nx] = True
                q.append([loc_nx, step[loc_nx-1], cnt + 1])
            elif loc_nx == N :
                minValue = cnt + 1
                sign = True
                break
        else :
            continue
        if sign :
            break
    return minValue

result = bfs()

if result == 101 :
    print(-1)
else :
    print(result)