[백준 - 2253][GOLD 4][해설 X] - 점프 (JAVA)

 

문제 링크

---

https://www.acmicpc.net/problem/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을 출력한다.

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        boolean[] invalid = new boolean[N+1];

        for(int i=0;i<M;i++){
            int stone = Integer.parseInt(br.readLine());

            invalid[stone] = true;
        }

        int minTime = -1;
        boolean[][] visited = new boolean[N+1][N+1];

        Queue<Person> q= new LinkedList<>();
        q.add(new Person(1,0,0));

        while(!q.isEmpty()){
            Person curr = q.poll();

            visited[curr.speed][curr.location] = true;

            if(curr.location == N){
                minTime = curr.time;
                break;
            }

            //현재 속도 -1 점프
            if(curr.speed - 1 > 0
                    && curr.location + curr.speed - 1 > 0
                    && curr.location + curr.speed - 1 <= N
                    && !visited[curr.speed - 1][curr.location + curr.speed - 1]
                    && !invalid[curr.location + curr.speed - 1]){
                visited[curr.speed - 1][curr.location + curr.speed - 1] = true;
                q.add(new Person(curr.location + curr.speed - 1,curr.time+1, curr.speed -1));
            }
            //현재 속도 점프
            if(curr.speed > 0
                    && curr.location + curr.speed > 0
                    && curr.location + curr.speed <= N
                    && !visited[curr.speed][curr.location + curr.speed]
                    && !invalid[curr.location + curr.speed]){
                visited[curr.speed][curr.location + curr.speed] = true;
                q.add(new Person(curr.location + curr.speed,curr.time+1, curr.speed));
            }
            //현재 속도 + 1 점프
            if(curr.location + curr.speed + 1 <= N
                    && !visited[curr.speed + 1][curr.location + curr.speed + 1]
                    && !invalid[curr.location + curr.speed + 1]){
                visited[curr.speed + 1][curr.location + curr.speed+1] = true;
                q.add(new Person(curr.location + curr.speed + 1,curr.time+1, curr.speed+1));
            }
        }

        System.out.println(minTime);
    }
}

class Person{
    int location;
    int time;
    int speed;

    public Person(int location, int time,int speed){
        this.location = location;
        this.time = time;
        this.speed = speed;
    }
}

 

 

실행 결과

---

 

팁

---

• 각 경우의 수의 조건을 잘 생각해서 방문배열을 만들자