문제 풀이(50)

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

import java.io.*;
import java.util.*;

class Node{
    int idx;
    int depth;

    Node(int idx,int depth) {
        this.idx = idx;
        this.depth = depth;
    }
}

public class Main {
    static int N;
    static int[] A; 

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        A = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 1; i <= N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        bfs(1);
    }

    public static void bfs(int start) {
        Queue<Node> Q = new LinkedList<>();
        boolean[] visited = new boolean[N + 1];  
        Q.offer(new Node(start, 0));
        visited[start] = true;

        while (!Q.isEmpty()) {
            Node now = Q.poll();

            if (now.idx == N) {
                System.out.println(now.depth);
                return;
            }

            int limit = now.idx + A[now.idx];
            for (int k = limit; k > now.idx; k--) {
                if (k <= N && !visited[k]) { 
                    visited[k] = true;
                    Q.offer(new Node(k, now.depth + 1));
                }
            }
        }

        System.out.println(-1);
    }
# }

1.BFS를 시작하기 전에 visited 배열을 선언하고, 시작점을 방문처리합니다.
2.시작점 Node를 큐에 넣는다.
3.큐가 빌 때까지 다음의 작업을 반복한다.

큐에서 하나의 Node를 꺼낸다.
해당 Node의 위치가 미로의 끝(N)이면 현재까지의 점프 횟수를 출력하고 종료한다.
현재 위치에서 점프할 수 있는 최대 거리를 계산한다.
최대 거리부터 현재 위치까지 역순으로 점프 가능한 모든 위치를 확인하면서 다음을 수행한다.
해당 위치를 방문하지 않았다면 방문 처리를 하고, 그 위치의 Node를 큐에 넣는다.

4.큐가 빌 때까지 도착점에 도달하지 못하면 -1을 출력한다.