백준 1520번
https://www.acmicpc.net/problem/1520
지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.
첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.
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
의 값을 이용해서 누적합을 만들어낸다.
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
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