문제를 보면 입력으로 숫자 배열을 받은 뒤, 현재 위치한 숫자 기준으로 오른쪽에 숫자 칸 만큼 이동할 수 있는데 배열의 끝까지 가는데 성공하면
움직인 횟수를 출력하고, 끝까지 가지 못했을 경우에는 -1을 출력해주면 끝이다
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 Main {
static int[] map;
static boolean[] visited;
static int ans = -1;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int count = Integer.parseInt(br.readLine());
map = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
visited = new boolean[map.length];
bfs(0);
System.out.println(ans);
}
public static void bfs(int start) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{start, 0});
while (!queue.isEmpty()) {
int[] poll = queue.poll();
visited[poll[0]] = true;
if (poll[0] == map.length - 1) {
if (ans == -1) {
ans = poll[1];
} else {
ans = Math.min(ans, poll[1]);
}
break;
}
for (int i = 1; i <= map[poll[0]]; i++) {
if (poll[0] + i < map.length) {
if (!visited[poll[0] + i]) {
queue.add(new int[]{poll[0] + i, poll[1] + 1});
visited[poll[0] + i] = true;
}
}
}
}
}
}
움직이는 경우의 수가 굉장히 많기 때문에 BFS를 사용해줘야 하는데, Queue에 이동할 수 있는 칸과 이동 칸수를 넣어 계속 이동시키면서, visited 배열을 사용해서 동일한 칸은 다시 방문하지 않도록 하고
Queue로 경우의 수를 모두 확인하다가 끝에 도달하면, 가장 작은 값만 갱신시키는 식으로 최소 횟수를 찾아 출력해주면 끝이다.
Leave a Reply