백준 1520번
https://www.acmicpc.net/problem/1520

문제

---

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.

생각하기

---

• 일반 DFS방식으로 탐색할 경우, 시간초과가 발생함
• Memoization을 사용해야 함 (동적 계획법)

동작

memo = new Integer[M][N]; // 아직 모른다 or 갈 수 없다 = null, 갈 수 있다 >= 1

Memoization을 담당하는 memo배열을 생성함.
Integer 배열로 만들어서 null값으로 초기화함.

여기서 null값은 갈 수 없다 또는 아직 모른다를 의미하고,
null을 제외한 정수 값은 갈 수 있다 와 간적이 있다를 의미한다.

	static int DFS(int x, int y) {
		
		if(x == M-1 && y == N-1) {
			return 1;
		}
		
		// 0이 아닐 경우, 방문 했음을 의미함
		if(memo[x][y] != null) {
			return memo[x][y];
		}
		
		memo[x][y] = 0;
		for(int i=0; i<4; i++) {
			nowX = x + dirX[i];
			nowY = y + dirY[i];
			
			if(!range_check()) continue;
			
			if(arr[x][y] > arr[nowX][nowY]) {
				memo[x][y] += DFS(nowX, nowY);		
			}
		}
		
		return memo[x][y];
	} // End of DFS

DP의 Top-Down 방식과 DFS를 합쳐서 메소드를 만들었다.

memo의 값을 이용해서 누적합을 만들어낸다.

코드

---

Java

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

public class Main {
	static int arr[][];
	static int dirX[] = {0, 0, -1, 1};
	static int dirY[] = {-1, 1, 0, 0};
	static Integer memo[][];
	
	static int nowX = 0; static int nowY = 0;
	static int N, M;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken()); // 가로
		N = Integer.parseInt(st.nextToken()); // 세로
		arr = new int[M][N];
		memo = new Integer[M][N]; // 아직 모른다 or 갈 수 없다 = null, 갈 수 있다 >= 1
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		System.out.print(DFS(0, 0)); // 출발은 (0, 0)
	} // End of main
	
	static int DFS(int x, int y) {
		
		if(x == M-1 && y == N-1) {
			return 1;
		}
		
		// 0이 아닐 경우, 방문 했음을 의미함
		if(memo[x][y] != null) {
			return memo[x][y];
		}
		
		memo[x][y] = 0;
		for(int i=0; i<4; i++) {
			nowX = x + dirX[i];
			nowY = y + dirY[i];
			
			if(!range_check()) continue;
			
			if(arr[x][y] > arr[nowX][nowY]) {
				memo[x][y] += DFS(nowX, nowY);		
			}
		}
		
		return memo[x][y];
	} // End of DFS

	static boolean range_check() {
		return nowX < M && nowX >= 0 && nowY < N && nowY >= 0;
	} // End of range_check
} // End of Main class

Kotlin

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

private lateinit var arr : Array<IntArray>
private lateinit var memo : Array<IntArray>
private val dirX = intArrayOf(0, 0, -1, 1)
private val dirY = intArrayOf(-1, 1, 0, 0)
private var N = 0; private var M = 0
private var nowX = 0; private var nowY = 0

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    var st = StringTokenizer(br.readLine())

    M = st.nextToken().toInt()
    N = st.nextToken().toInt()
    arr = Array(M){IntArray(N) {0}}
    memo = Array(M){IntArray(N) {-1}}

    for(i in 0 until M) {
        st = StringTokenizer(br.readLine())
        for(j in 0 until N) {
            arr[i][j] = st.nextToken().toInt()
        }
    }
    
    println(DFS(0, 0))
} // End of main

private fun DFS(x : Int, y : Int) : Int {

    if(x == M-1 && y == N-1) return 1
    if(memo[x][y] != -1) return memo[x][y] // -1이 아닐 경우, 이미 방문을 했음을 의미함

    memo[x][y] = 0
    for(i in 0 until 4) {
        nowX = x + dirX[i]
        nowY = y + dirY[i]

        if(!rangeCheck()) continue
        if(arr[x][y] > arr[nowX][nowY]) memo[x][y] += DFS(nowX, nowY)
    }

    return memo[x][y]
} // End of DFS

private fun rangeCheck() : Boolean {
    return nowX < M && nowX >= 0 && nowY < N && nowY >= 0
} // End of rangeCheck