11060-점프점프

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

11060번: 점프 점프

[문제 요약]

• 1XN 크기의 미로
• 현재위치는 미로의 가장 왼쪽 끝, 가장 오른쪽 끝으로 진행한다.
• 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. (3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.)

 

[문제 풀이]

• 각각 지점의 위치와 해당 위치까지 이동한 횟수를 저장하기 위해 nTime 객체 생성
• 현재 처음 위치(0) 부터 진행되는 BFS를 시작
• 문제의 예시와 같이 현재 위치 idx부터 다음 +nidx까지 이동할때 조건에 부합하는지 확인하고 방문한다.
  • nidx가 최대길이N을 초과하는지
  • arr[nidx]의 값이 0이 아닌지
  • 이미 방문을 한 장소인지 (visited[nidx])
• 방문할 위치와 진행 횟수를 새로운 객체로 만들어서 큐에 넣는다.
• 큐에서 꺼낸 객체 번호가 최대길이(N)과 같다면 해당 객체의 횟수를 반환하여 BFS를 종료한다.

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class 점프점프 {

    static int num;
    static int[] arr;

    static class nTime {

        int idx;
        int cnt;

        public nTime(int idx, int cnt) {
            this.idx = idx;
            this.cnt = cnt;
        }
    }

    public static int bfs(nTime root, boolean[] visited) {

        Queue<nTime> queue = new LinkedList<>();
        visited[root.idx] = true;

        queue.offer(root);

        while(!queue.isEmpty()) {

            nTime tmp = queue.poll();
            if(tmp.idx == arr.length-1) return tmp.cnt;

            for(int i = 1; i <= arr[tmp.idx]; i++) {
                int nidx = tmp.idx + i;
                if(nidx < num && arr[tmp.idx] != 0 && !visited[nidx]) {
                    queue.offer(new nTime(nidx, tmp.cnt+1));
                    visited[nidx] = true;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        num = Integer.parseInt(bf.readLine());
        arr = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        boolean[] visit = new boolean [num];

        nTime nTime = new nTime(0, 0);
        System.out.println(bfs(nTime, visit));
    }
}