99클럽 코테 스터디 31일차 TIL , 점프 점프

문제

풀이

입력으로 돌의 개수와 돌에서 점프할 수 있는 거리 그리고 시작점이 주어진다.

시작점에서 출발하여 갈 수 있는 돌들의 개수를 출력하면 된다.

 

제출 1 - 정답

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

public class Main {
    static int answer = 0;
    static boolean[] check;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] ai = new int[n];
        check = new boolean[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            ai[i] = Integer.parseInt(st.nextToken());
        }
        int s = Integer.parseInt(br.readLine());

        dfs(n, ai, s-1);

        System.out.println(answer);
    }

    private static void dfs(int n, int[] ai, int idx) {
        if(!check[idx]){
            check[idx] = true;
            answer++;
        }
        int val = ai[idx];
        if(idx + val < n){
            dfs(n, ai, idx + val);
        }
        if(idx - val >= 0){
            dfs(n, ai, idx - val);
        }
    }
}

 

check를 만들어 체크될 때 개수를 세어준다.

check를 미리 검사하여 조건문을 제거해 주면 시간이 덜 걸릴 거 같아 아래와 같이 해봤는데

private static void dfs(int n, int[] ai, int idx) {
        check[idx] = true;
        answer++;
        
        int val = ai[idx];
        if(idx + val < n && !check[idx + val]){
            dfs(n, ai, idx + val);
        }
        if(idx - val >= 0 && !check[idx - val]){
            dfs(n, ai, idx - val);
        }
    }

 

얼마 차이 안난다.

TIL

• dfs