[swjungle 2기] 백준 2253 점프

2253번: 점프

- dp로 해보려다 많은 실패후 찾아보니 bfs로 풀이가 가능하다는 것을 알고 호다닥 해보았습니다.

- 탐색을 하면서 같은 돌을 방문시 그 당시 속도까지 저장을 해주어 추후에 방문했을때 같은속도면 이미 한번 탐색을 한 것으로 간주하고 넘어갑니다.

 

# 2253 점프
from collections import deque
import sys
N, M = map(int, sys.stdin.readline().split())
check = [[] for _ in range(N + 1)]
# 리스트로하면 시간초과남
small = set()
for _ in range(M):
    small.add(int(sys.stdin.readline().strip()))


def jumpRock(N, check, small):
    q = deque()
    q.append((1, 0, 0))
    while q:
        curr_rock, move, cnt = q.popleft()
        for jump in [move-1, move, move+1]:
            if jump > 0:
                next_rock = curr_rock + jump
                if next_rock == N:
                    return cnt + 1
                if next_rock > N:
                    continue
                if move not in check[next_rock] and next_rock not in small:
                    check[next_rock].append(jump)
                    q.append((next_rock, jump, cnt+1))

    return -1


print(jumpRock(N, check, small))

 

- 멈출 수 없는 작은 돌을 저장할 때 리스트로 저장하면 시간초과가 나서 돌의 숫자는 (1 ,2 3,4. ... N)  중복이 되지 않기 때문에 set으로 수정하였습니다.