[BOJ] 14248 점프점프

점프점프

풀이

• 돌다리에 숫자가 적혀있고, 이 숫자가 적혀있는 만큼 왼쪽이나 오른쪽으로 점프할 수 있다.
• 자기가 방문 가능한 돌들의 개수를 알고 싶다.
• 출발점 s가 주어진다.
• bfs 로 풀었다. 숫자가 적혀있는 만큼 왼쪽, 오른쪽으로 점프하는 두개의 경우만 고려해서 탐색하면 됨.
• 방문처리 할 때마다 answer+=1 을 수행함

코드

import java.util.*;
import java.io.*;
public class Main {
    static int[] map;
    static boolean[] visited;
    static int answer;
    static int n;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n+1];
        visited = new boolean[n+1];
        answer = 1;
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1;i<=n;i++){
            map[i] = Integer.parseInt(st.nextToken());
        }
        int start = Integer.parseInt(br.readLine());
        bfs(start);
        System.out.println(answer);
    }

    public static void bfs(int x) {
        visited[x] = true;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(x);

        while(!queue.isEmpty()){
            int cur = queue.poll();
            int dx = map[cur];
            int nx = cur+dx;
            if(nx>=1 && nx<=n && !visited[nx]){
                answer++;
                visited[nx] = true;
                queue.add(nx);
            }
            nx = cur-dx;
            if(nx>=1 && nx<=n && !visited[nx]){
                answer++;
                visited[nx] = true;
                queue.add(nx);
            }
        }
    }
}