문제

https://www.acmicpc.net/problem/1520

요약

간단히 내용을 요약하면 왼쪽위에서 오른쪽아래 칸으로 가는경우를 구하는데 칸의 값이 낮아지는 방향으로 진행되다는 조건이 있다
0<= N,M < 500
칸의 값은 10000이하의 자연수이다. (0은 자연수다)

풀이

500 ^ 2 의 모든 칸을 조사해 경우의수르 따지는 완탐을 사용하면 꽤 많은 수가 나오게 된다. 그렇기 때문에 dp 를 활용하거나 그리디 를 활용해야한다.
찾으면서 값을 갱신하는 형태의 dp 를 활용하기로 결정했고
dp 함수의 정의는 해당 칸에서 목적지에 도착할수 있는 경우의 수를 삼아
진행하면서 합해가는 형태로 만들었다.
특징으로라면
-1 로 dp 를 초기화한 부분인데 그이유는 해당 칸이 목적지에 도착할수 있는 경우가 0인경우가 있기때문이다 여기서 방문을 별도로 관리하면 메모리가 초과날수도 있다는 생각이 들었다.

로직

피보나치 + 메모이제이션과 유사한 구조
1. 0,0 에서 부터 dp 에 값이 없다면 재귀를 시도한다
2. 만약 -1 값이라면 0으로 초기화한다.
3. 값이 가능한값 (점점커지근 값 && 내부에 있다면) 이라면 dp 누산시킨다.

코드

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

/**
 * 탑다운 방식
 * dp[][]  해당칸에서 목적지 도착하는 경우 
 * 1. 기록된게 없다면 재귀타고 찾아온다 끝 닿을때까지
 * 2.  처음 방문하면 0으로 바꿔줘라
 * 방문처리를 배열로 하면 메모리 초과 (계속 넘겨줘야한다.)구할때 -1 이면 찾으러 가라 하자 like 피보나치 + 메모이제이션
 * 내려막이기때문에 역주행 막을수 있다
 */
public class Main {
	static int N;
	static int M;
	static int[][] dp;
	static int[][] input;
	static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		dp = new int[M][N];
		input = new int[M][N];
		for (int[] d : dp) {
			Arrays.fill(d, -1);
		}
		for (int row = 0; row < M; row++) {
			st = new StringTokenizer(br.readLine());
			for (int col = 0; col < N; col++) {
				input[row][col] = Integer.parseInt(st.nextToken());
			}
		}
		System.out.println(dfs(0, 0));


	}

	private static int dfs(int row, int col) {
		if (row == M - 1 && col == N - 1) {
			return 1; // 닿으면 한개 리턴
		}

		if (dp[row][col] != -1) {
			return dp[row][col]; // 값이 있다면 돌려줘라
		}
		dp[row][col] = 0; //일단 초기화
		for (int[] d : dir) {
			int nextRow = row + d[0];
			int nextCol = col + d[1];

			if (isIn(nextRow, nextCol) && input[row][col] > input[nextRow][nextCol]) {

				dp[row][col] += dfs(nextRow, nextCol); // 값더해주기

			}
		}
		return dp[row][col];
	}



	private static boolean isIn(int row, int col) {
		return row < M && row >= 0 && col < N && col >= 0;
	}
}

시행착오

처음에 완탐으로 진행했다가 메모리터지고 확인해보니 128mb 이였다.
이후 dfs 의 check 부분을 좀 없에려는 여러시도를 해보다 결국 해답은 dp 라 생각했다.

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

/**
 * 2초 시간이 오래 걸려도 하나의 배열에 담는 방법 없을까..
 * 각점별로 가능성을 보기
 *
 */

public class Main {
	static int N;
	static int M;
	static int[][] input;
	static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
	static int count = 0;
	static int testCount = 0;
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		input = new int[N][M];
		for (int row = 0; row < N; row++) {
			st = new StringTokenizer(br.readLine());
			for (int col = 0; col < M; col++) {
				input[row][col] = Integer.parseInt(st.nextToken());
			}
		}
		boolean[][] check = new boolean[N][M];
		check[0][0] = true;
		dfs(0, 0);
		System.out.println(count);
	}

	private static void dfs(int row, int col) {
		testCount++;
		if (row == N - 1 && col == M - 1) {
			count++;
			return;
		}
		for (int d = 0; d < 4; d++) {
			int nextRow = row + dir[d][0];
			int nextCol = col + dir[d][1];
			if (isIn(nextRow, nextCol) && input[nextRow][nextCol] < input[row][col]) {
				for (int brow = 0; brow < N; brow++) {
					for (int bcol = 0; bcol < M; bcol++) {
					}
				}
				dfs(nextRow, nextCol);
			}
		}

	}

	private static void printArr(boolean[][] arr) {
		System.out.println();
		for (boolean[] br : arr) {
			for (boolean b : br) {
				System.out.print(b ? 1 : 0);
			}
			System.out.println();
		}
	}

	private static boolean isIn(int row, int col) {
		return row < N && row >= 0 && col < M && col >= 0;
	}
}