[Algorithm Study] 백준 11060

문제 출처 : https://www.acmicpc.net/problem/11060

문제 접근

위의 문제를 읽으면 1XN으로 이루어진 미로에 대해서 각 자리마다 정해진 수 만큼 이동이 가능합니다. 각자리에 대한 배열을 생성한 뒤에 방문순서를 기록하고 마지막 위치에 기록된 수가 0인 경우, 끝까지 도달을 못한 것으로 판단했고 그렇지 않은 경우에는 끝까지 도달한 것으로 보아 최소 점프를 횟수를 출력하도록 BFS를 활용하여 문제를 해결했습니다.

소스 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int[] map = new int[N];
        int[] check = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){ // 맵 생성
            map[i] = Integer.parseInt(st.nextToken());
        }
        int index = 0;
        Queue<Integer> q = new LinkedList<>();
        q.offer(map[index]);
        while(!q.isEmpty()){
            int y = q.poll(); // 큐에서 꺼내는 것
            int visit = check[index]; // 이전 값 넣기
            for(int i = 0; i < y; i++){
                index++;
                if(index >= N){
                    break;
                }
                if(check[index] == 0){
                    check[index] = visit + 1;
                    q.offer(map[index]);
                }
            }
            if(y == 0){
                index++;
            }
            for(int i = 0; i < y-1; i++){
                index--;
            }
        }
        if(N == 1){
            System.out.println(0);
        }
        else if(check[N-1] == 0){
            System.out.println(-1);
        }
        else{
            System.out.println(check[N-1]);
        }
    }
}