백준 11060: 점프 점프[JAVA]

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

 

[난이도]

- Silver 2

 

[알고리즘]

- bfs

 

[코드]

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

public class Main {
    static int N;
    static int[] maze;
    static boolean[] visited;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        maze = new int[N];
        visited = new boolean[N];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            maze[i] = Integer.parseInt(st.nextToken());
        }
        bfs();
    }
    static void bfs() {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        visited[0] = true;
        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int cur = tmp[0];
            int count = tmp[1];
            if (cur == N - 1) { // 도착했다면
                System.out.println(count); // count 출력
                return;
            }
            for (int i = 1; i <= maze[cur]; i++) {
                if (cur + i < N) { // 최대 인덱스를 넘어서지 않는 경우에만
                    if (!visited[cur + i]) { // 방문하지 않은 경우
                        queue.offer(new int[]{cur + i, count + 1});
                        visited[cur + i] = true;
                    }
                }
            }
        }
        System.out.println(-1); // 도착실패 시 출력
    }
}

 

[풀이]

DP로 풀 수 있는문제이다. 하지만 BFS로 풀었다.

1. 큐에 현재 위치와 몇번 점프했는지를 담는다.

2. 현재위치에서 이동가능한 만큼 반복하며 큐에 담는다. 큐에 담을때 이동했을 때의 위치와 현재까지 점프한 횟수 + 1를 해 큐에담는다.

이 때 이동했을 때의 위치가 최대 인덱스를 넘어서면 메모리초과가 발생하기 때문에 아닌경우에만 하고 방문하지 않은경우에만 큐에 담아준다.

3. 도착했다면 큐에담긴 count를 출력해주고 큐가 empty가 되어서 도착실패시 -1을 출력해준다.