문제:
N x N 크기의 바둑판이 있다. 각 칸에는 점프 할 수 있는 칸수가 적혀져있고, 오른쪽 또는 아래로만 이동이 가능하다.
좌측상단에서 우측하단까지 이동해야한다.
첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.
가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 2^63-1보다 작거나 같다.
풀이:
경로 개수는 2^63-1보다 작거나 같으므로 꽤 많은 경우의 수가 나올 수 있다.
이럴때 BFS를 이용하면 메모리초과, DFS를 이용하면 시간초과가 나올 것이다.
이 문제는 경우의 수를 구하는 것으로, 각 칸에서 점프를 하며 다음 칸의 경우의 수에 + 1만 해주면 된다.
먼저 아래와 같이 입력을 받아준다.
static int N;
static int[][] jump;
static long[][] dp;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
jump = new int[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
jump[i][j] = Integer.parseInt(st.nextToken());
}
}
dp = new long[N][N];
dp[0][0] = 1;
routeCount();
System.out.println(dp[N - 1][N - 1]);
}- jump 배열은 각 칸의 점프 칸수를 저장한다.
- dp는 각 칸을 갈 수 있는 경우의 수를 저장한다.
고로 시작점인 dp[0][0]에는 1이 저장된다..
routeCount() 메서드는 아래와 같다.
static void routeCount() {
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
if (dp[y][x] == 0) {
continue;
}
if (jump[y][x] == 0) {
break;
}
if (y + jump[y][x] < N) {
dp[y + jump[y][x]][x] += dp[y][x];
}
if (x + jump[y][x] < N) {
dp[y][x + jump[y][x]] += dp[y][x];
}
}
}
}- 만약 dp[y][x]가 0이면 건너뛴다. 자세한 설명은 아래에서 하겠다.
- 만약 jump[y][x]가 0이면 목적지에 도달한 것이니 반복을 종료한다.
- 아래로 점프 했을 때, 범위에서 벗어나지 않았다면
- 점프한 칸에 지금 칸에 도착할 수 있는 경우의 수를 더해준다.
- 오른쪽으로 점프 했을 때, 범위에서 벗어나지 않았다면
- 점프한 칸에 지금 칸에 도착할 수 있는 경우의 수를 더해준다.
- 1~4번 과정을 시작점(0,0)에서 목적지(N-1, N-1)까지 반복한다.
dp[][]에 0이 담겨있다면, 이는 시작점에서 도달할 수 없는 위치라는 의미이다.
해당 위치에 도달하기 전에, 미리 해당 위치에 갈 수 있는 경우의 수가 결정되어 있기 때문이다.
만약 dp에 0이 담겨있는걸 검사하지 않는다면, 모든 칸에대해 검사를 해야 할 것이다.
전체코드:
import java.io.*;
import java.util.*;
public class 점프_1890번 {
static int N;
static int[][] jump;
static long[][] dp;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
jump = new int[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
jump[i][j] = Integer.parseInt(st.nextToken());
}
}
dp = new long[N][N];
dp[0][0] = 1;
routeCount();
System.out.println(dp[N - 1][N - 1]);
}
static void routeCount() {
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
if (dp[y][x] == 0) {
continue;
}
if (jump[y][x] == 0) {
break;
}
if (y + jump[y][x] < N) {
dp[y + jump[y][x]][x] += dp[y][x];
}
if (x + jump[y][x] < N) {
dp[y][x + jump[y][x]] += dp[y][x];
}
}
}
}
}
시행착오:
몇번의 경우가 나오는지 체크도 안하고, BFS를 이용하면 쉽게 풀 수 있을 것이라 생각했다.
하지만 무려 경로 개수는 2^63-1보다 작거나 같으므로 메모리 초과가 일어났다.
public class 점프_1890번_메모리초과 {
static int N;
static int[][] jump;
static int[][] sum;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
jump = new int[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
jump[i][j] = Integer.parseInt(st.nextToken());
}
}
sum = new int[N][N];
sum[0][0] = 1;
routeCount();
System.out.println(sum[N - 1][N - 1]);
}
static void routeCount() {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{0, 0});
while (!queue.isEmpty()) {
int[] now = queue.poll();
int nowY = now[0];
int nowX = now[1];
if (nowX == N - 1 && nowY == N - 1) {
continue;
}
if (nowY + jump[nowY][nowX] < N) {
queue.add(new int[]{nowY + jump[nowY][nowX], nowX});
sum[nowY+ jump[nowY][nowX]][nowX] += sum[nowY][nowX];
}
if (nowX + jump[nowY][nowX] < N) {
queue.add(new int[]{nowY, nowX + jump[nowY][nowX]});
sum[nowY][nowX + jump[nowY][nowX]] += sum[nowY][nowX];
}
}
}
}
혹시나 하고 dfs도 해봤지만, 당연하게도 시간초과가 발생했다.
재귀로 왔다 갔다 하기에는 시간이 너무 오래걸리기 때문이다.
이후 dp를 사용해서 문제를 풀었을 때도, 불필요한 코드를 작성했는데,
dp[y][x] == 0이면 들를 필요가 없음애도, visited 배열을 작성했었다.
dp가 아직 익숙치 않은 듯 하다. 더더욱 반복해보자.