[BOJ]2253. 점프 (python)

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

2253번: 점프

 

문제

N(2 ≤ N ≤ 10,000)개의 돌들이 같은 간격으로 놓여 있다. 편의상 순서대로 1, 2, …, N번 돌이라고 부르자. 당신은 현재 1번 돌 위에 있는데, 이 돌들 사이에서 점프를 하면서 N번째 돌로 이동을 하려 한다. 이때 다음 조건들이 만족되어야 한다.

1. 이동은 앞으로만 할 수 있다. 즉, 돌 번호가 증가하는 순서대로만 할 수 있다.
2. 제일 처음에 점프를 할 때에는 한 칸밖에 점프하지 못한다. 즉, 1번 돌에서 2번 돌이 있는 곳으로 점프할 수 있다. 그 다음부터는 가속/감속 점프를 할 수 있는데, 이전에 x칸 점프를 했다면, 다음번에는 속도를 줄여 x-1칸 점프하거나, x칸 점프하거나, 속도를 붙여 x+1칸 점프를 할 수 있다. 물론 점프를 할 때에는 한 칸 이상씩 해야 한다.
3. 각 돌들은 각기 그 크기가 다르고, 그 중 몇 개의 돌은 크기가 너무 작기 때문에 당신은 그러한 돌에는 올라갈 수 없다.

위와 같은 조건들을 만족하면서 1번 돌에서 N번 돌까지 점프를 해 갈 때, 필요한 최소의 점프 횟수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 N, M(0 ≤ M ≤ N-2)이 주어진다. M은 크기가 맞지 않는, 즉 크기가 작은 돌의 개수이다. 다음 M개의 줄에는 크기가 작은 돌들의 번호가 주어진다. 1번 돌과 N번 돌은 충분히 크기가 크다고 가정한다.

출력

첫째 줄에 필요한 최소의 점프 횟수를 출력한다. 만약 N번 돌까지 점프해갈 수 없는 경우에는 -1을 출력한다.

 

 

풀이

## 아쉬운 풀이입니다...! 최적의 코드를 찾는다면 비추합니다.

 

DP와 BFS중 BFS 풀이를 이용했다.
https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

이 문제와 유사하게 풀었다. (더 쉬운 문제이니 참고하면 좋을듯하다)

 

현재 위치와 점프하는 거리(dist)를 2차원 배열에 저장한다.
같은 곳을 같은 속도로 방문했었다면 확인하지 않고 넘어간다! (늦게 저장되는 경우는 더 오랜 시간이 걸린 것이므로)

 

 

 

DP를 이용한 풀이 다시 작성하기!

 

코드

import sys
import collections
read = sys.stdin.readline

stone_N, small_stone_M = map(int, read().strip().split())

small_stone = [int(read().strip()) for _ in range(small_stone_M)]


queue = collections.deque()




def bfs(x, dist):
    visted = [[0] * (stone_N + 1) for _ in range(int((2 *stone_N) ** 0.5) + 1)]
    visted[dist][x] = 1
    queue.append((x, dist, 0))
    while queue:
        now_x, jump_dist, count = queue.popleft()

        for dx in [-1, 0, 1]:
            new_dist = jump_dist + dx
            new_x = now_x + new_dist
            if new_x in small_stone:
                continue
            if 0 < new_dist and new_x <= stone_N and visted[new_dist][new_x] == 0:
                queue.append((new_x, new_dist, count + 1))
                visted[new_dist][new_x] = 1
            if new_x == stone_N:
                return count + 1
    return -1
print(bfs(1, 0))