[Baekjoon] 백준 14248번: 점프 점프 (JAVA)

문제 14248

14248번: 점프 점프

 

[ 풀이 과정 ]

입력값을 살펴보면, 돌의 개수를 입력받은 후 각 돌의 위치에서 좌우로 점프할 수 있는 거리, 즉 칸의 개수를 입력받습니다. 따라서 jump[]에 각 위치에서 점프할 수 있는 거리를 입력 받아 저장해주고,  BFS를 사용하여 현재 칸에서 점프하여 갈 수 있는 모든 위치를 큐에 넣고 방문표시를 해준 후, 전역변수 cnt를 하나씩 증가해줍니다.

[ 코드 ]

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static int[] jump;
    private static Queue<Integer> queue = new LinkedList<>();
    private static boolean[] visit;
    private static int[] move = {-1, 1}; // 좌우 이동

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        jump = new int[N+1];
        visit = new boolean[N+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=1; i<=N; i++) {
            jump[i] = Integer.parseInt(st.nextToken());
        }

        int init = Integer.parseInt(br.readLine());
        visit[init] = true;
        queue.offer(init);
        int cnt = 1;
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int i=0; i<2; i++) {
                int next = cur + jump[cur]*move[i];
                if (next < 1 || next > N) continue;
                if (visit[next]) continue;
                visit[next] = true;
                queue.offer(next);
                cnt++;
            }
        }

        bw.write(String.valueOf(cnt));
        bw.flush();
    }
}