백준 14248 자바 - 점프 점프 (BOJ 14248 JAVA)

문제 : boj14248

 

 

  문제 자체의 정의에 따라 i번째 정점에서 i-Ai, i+Ai 로의 간선이 생긴다. 이에 대해 단순히 방문 가능한 위치만 찾으면 되므로 dfs 혹은 bfs로 더이상 진행 불가할때까지 진행해보면서 방문한 곳의 개수를 세면 된다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    boolean[] v;
    int cnt = 0, n;
    int[] arr;

    private void dfs(int s) {
        if (s<1||s>n||v[s]) return;

        v[s] = true;
        cnt++;
        dfs(s+arr[s]);
        dfs(s-arr[s]);
    }

    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        arr = new int[n+1];
        v = new boolean[n+1];
        for (int i = 1; i <= n; i++) arr[i] = Integer.parseInt(st.nextToken());

        int s = Integer.parseInt(br.readLine());

        dfs(s);
        System.out.println(cnt);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}