11주차 : DFS/BFS 문제2

✔BOJ_11060

bfs를 이용하여 문제를 풀었느데 시간초과가 떴습니다 :( 그래서 검색 후에 다이나믹 프로그래밍으로 쓰는 방법을 알어냈습니다.

bfs를 이용한 방식은 다음과 같습니다.

package BaekJoon.DFSBFS;

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

public class BOJ_11060 {
    static int map[];
    static int n;
    static boolean check[];
    static Stack<Integer> stk;
    static int count ;

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

        count = Integer.MAX_VALUE;
        bfs(0,0);
        if(count == Integer.MAX_VALUE){
            count = -1;
        }
        System.out.println(count);

    }
    private static void bfs(int a, int cnt) {
        if(a < 0 || a>=n){return;}
        if(a == (n-1)) {
            if(cnt < count ) count = cnt;
            return;
        }
        int tmp = map[a];
        cnt++;
        for(int i=tmp; i>=1; i--){
//            System.out.println("a+1 = " + (a + 1));
//            System.out.println("cnt++ = " + ++cnt);
            bfs(a+i, cnt);
        }
    }
}

다이나믹 프로그래밍으로 dp 배열에 count개수를 저장하는 방식입니다. 어떤 부분에서 속도가 개선되는지는 잘 모르겠지만..

package BaekJoon.DFSBFS;

import java.util.Arrays;
import java.util.Scanner;

public class BOJ_11060_adv {
    static int N;
    static int[] A;
    static int[] dp;

    // 작은 문제부터 풀기
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        N = sc.nextInt();
        // 다이나믹 프로그래밍 사용
        A = new int[N+1];
        for(int i=1;i<=N;i++){
            A[i] = sc.nextInt();
        }

        dp = new int[N+1];
        Arrays.fill(dp, Integer.MAX_VALUE);

        dp[1] = 0;
        for(int i=1;i<=N;i++){
            if(dp[i] != Integer.MAX_VALUE){
                int jump = A[i];
                for(int j=1;j<=jump;j++){
                    if(i+j >N) continue;
                    dp[i+j] = Math.min(dp[i]+1, dp[i+j]);
                }
            }
        }
        System.out.println(dp[N] == Integer.MAX_VALUE ? -1 : dp[N]);

    }

}