(백준/자바) 힌트문제3 04. 다이나믹 프로그래밍 - 백준 1890번 문제 : 점프

1890번: 점프 (acmicpc.net)

1890번: 점프

다이나믹 프로그래밍... 공부 하고 와야겠다.

 

---

8/8

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

class Main {
    static int d[][] = {{0,1}, {1,0}};
    static int N;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int arr[][] = new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        System.out.println(bfs(arr, 0, 0));
    }
    public static long bfs(int [][]arr, int sRow, int sCol) {
        Queue<Point> q = new LinkedList<>();
        boolean visited[][] = new boolean[N][N];
        q.offer(new Point(sRow, sCol));
        visited[sRow][sCol] = true;
        long answer = 0;
        while (!q.isEmpty()) {
            Point cur = q.poll();

            for (int i = 0; i < 2; i++) {
                int dx = cur.row + d[i][0];
                int dy = cur.col + d[i][1];

                if (i == 0) {
                    dy += (arr[cur.row][cur.col] - 1);
                } else {
                    dx += (arr[cur.row][cur.col] - 1);
                }

                if (dx >= N ||  dy >= N || visited[dx][dy]) {
                    continue;
                }
                if (arr[dx][dy] == 0) {
                    answer ++;
                    visited[dx][dy] = false;
                }
                if (!visited[dx][dy] && arr[dx][dy] != 0) {
                    q.offer(new Point(dx, dy));
                    visited[dx][dy] = true;
                }

            }
        }
        return answer;
    }
    static class Point {
        int row,col;

        public Point(int r, int c) {
            this.row = r;
            this.col = c;
        }
    }
}

Queue를 이용한 BFS로 풀어봤으나 하나의 위치에서 오른 쪽으로 가도, 아래로 가도 경로가 될 때 visited 배열로 이미 true가 되어있어서 세지 못 한다.

 

dp를 이용해야한다.

dp[x][y] = x, y까지 도달할 수 있는 경우의 수 !

이렇게 dp 테이블을 구성해보면

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

class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long dp[][] = new long[N][N];
        int arr[][] = new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        dp[0][0] = 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i == N - 1 && j == N - 1) {
                    break;
                }
                int cnt = arr[i][j];
                if (i + cnt < N) {
                    dp[i + cnt][j] += dp[i][j];
                }
                if (j + cnt < N) {
                    dp[i][j + cnt] += dp[i][j];
                }
            }
        }
  
        System.out.println(dp[N - 1][N - 1]);
    }
}

정말 간단하게 풀 수 있다 ㅠ 테이블을 어떻게 구성할 지를 잘 떠올려보자 ,  , 

 

그리고 for문 중첩으로 입력 받을 때

for (int i = 0; i < n; i++) {
	String[] input = br.readLine().split(" ");
	for (int j = 0; j < n; j++) {
		arr[i][j] = Integer.parseInt(input[j]);
	}
}

이렇게 하면 더 간단하게 할 수 있구나 ! 읽어들인 한 줄을 공백으로 구분해서 String형 배열에 넣은 다음에 하나 씩 넣으면 된다 !