[백준] 1890. 점프 (Java)

 

1890번: 점프

 

DP문제이고 두 가지 방식으로 풀 수 있다.

 

Top-Down

풀이

• DFS 재귀를 이용한다.
• 목적지인 arr[N - 1][N - 1]에 도달했을 경우 1을 return한다.
• 처음 방문하는 위치일 경우에만 DFS를 수행한다.
  • 정답일 경우 1이 계속 return하면서 올 것이므로 cnt[x][y] += solve(nx, ny); 을 해준다.
  • 그렇지 않으면 기존 값 (cnt[x][y])을 return한다.
• 방문체크는 처음에 cnt배열을 -1로 초기화한 후 방문할 시 0으로 값을 변경한다.

코드

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

public class Main {
    static int N;
    static int[][] arr;
    static long[][] cnt;
    static int[] px = new int[]{1, 0};
    static int[] py = new int[]{0, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];
        cnt = new long[N][N];

        for (long[] col : cnt)
            Arrays.fill(col, -1);

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++)
                arr[i][j] = Integer.parseInt(st.nextToken());
        }

        solve(0, 0);

        bw.write(String.valueOf(cnt[0][0]));
        br.close();
        bw.close();
    }

    public static long solve(int x, int y) {
        if (x == N - 1 && y == N - 1) {
            return 1;
        }

        if (cnt[x][y] == -1) {
            cnt[x][y] = 0;
            for (int d = 0; d < 2; d++) {
                int nx = x + px[d] * arr[x][y];
                int ny = y + py[d] * arr[x][y];

                if (!isIn(nx, ny)) continue;
                cnt[x][y] += solve(nx, ny);
            }
        }

        return cnt[x][y];
    }

    public static boolean isIn(int x, int y) {
        if (x < 0 || x >= N || y < 0 || y >= N) return false;
        return true;
    }
}

 

Bottom-Top

풀이

Queue를 사용하여 BFS를 할 경우 메모리 초과가 난다.

• N이 최대 100이기 때문에 이중 for문으로 탐색이 가능하다.
  • 0 <= x, y < N 이중 for문으로 돈다.
• 처음 cnt[0][0] 값은 1로 설정 후 다음 위치가 갈 수 있는 위치일 경우 다음위치 경로값 += 현재위치 경로값을 해준다.
• 다음 위치에 갈 수 있는 경로의 경우의 수를 넣는 것이기 때문에 방문체크는 현재 cnt[x][y]값이 0인 경우 방문할 수 없는 곳으로 판단하고 가지 않는다.

코드

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

public class Main {
    static int N;
    static int[][] arr;
    static long[][] cnt;
    static int[] px = new int[]{1, 0};
    static int[] py = new int[]{0, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];
        cnt = new long[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++)
                arr[i][j] = Integer.parseInt(st.nextToken());
        }

        cnt[0][0] = 1;


        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                if (x == N - 1 && y == N - 1) break;

                if (cnt[x][y] == 0) continue;

                for (int d = 0; d < 2; d++) {
                    int nx = x + px[d] * arr[x][y];
                    int ny = y + py[d] * arr[x][y];

                    if (!isIn(nx, ny)) continue;
                    cnt[nx][ny] += cnt[x][y];
                }
            }
        }

        bw.write(String.valueOf(cnt[N - 1][N - 1]));
        br.close();
        bw.close();
    }


    public static boolean isIn(int x, int y) {
        if (x < 0 || x >= N || y < 0 || y >= N) return false;
        return true;
    }
}

 

시간은 둘 다 비슷하게 130ms 언저리로 소요되었다.