[백준] JAVA - 1520.내리막길

입력조건 범위를 대충 확인하고 DFS로 풀어야지ㅎㅎ 했다가 시간초과가 나서 다시 DP로 풀었습니다. 테스트 케이스는 맞는데 시간초과가 뜨면 너무 슬프네요ㅠㅠ

 

시간초과가 난 이유는 사방탐색에 재귀로 계속 다음단계를 정하러 들어가므로 4의 (N*M)제곱 이 되기때문에 약 4의 500*500 제곱번의 연산을 수행하게 됩니다.

 

제가 정의한 DP[i][j] 는 시작좌표인 (0,0) 에서 (i,j)로 갈수있는 경로수의 합입니다. 이떄 초기 dp의 값을 -1로 초기화를 해줘야 합니다. 만약 이렇게 해주지 않으면 내리막길로 이동을 하다가 멈추는 지점이 존재할수있는데 그 지점에서의 dp 값은 0이 됩니다. 여기서 초기값을 0으로 해주었으면 같은 경우라고 판단하기때문에 연산을 다시 수행하게 됩니다. 따라서 -1로 초기화를 해줘야 합니다.

 

1. 사방탐색을 진행하면서 경우의 수를 더하면서 진행합니다.

2. 기저조건이 도착지점에 도착했을때이므로 1을 리턴해줍니다. 시작점부터 도착점까지 다음 단계로 계속 진행하지만 기저 조건을 통해 도착점부터 거꾸로 dp 값이 채워진다고 생각하면 됩니다.

3. 마스킹 처리를 해줬기 때문에 이미 갔던곳은 가지 않습니다.

package com.java.algorithm;

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

public class Baekjoon_1520_내리막길 {
/**
 * 왼쪽위 -> 오른쪽아래 : 현재값보다 낮은값으로만 이동 가능
 * dp[i][j] : 시작점에서 (i , j) 갈수있는 경로 수의 합.
 * 항상 내리막길로만 이동가능한 경로 수  출력
 */
	static int[][] map;
	static int R,C;
	static int[] dy = {-1,1,0,0}; // 상 하 좌 우
	static int[] dx = {0,0,-1,1}; // 상 하 좌 우
	static int[][] dp;
	static int answer = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String[] init = br.readLine().split(" ");
		R = Integer.parseInt(init[0]);
		C = Integer.parseInt(init[1]);
		
		map = new int[R][C];
		dp = new int[R][C];
		
		for (int i = 0; i < R; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < C; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				dp[i][j] = -1; //방문 여부 체크를 위해 -1 로 마스킹
			}
		}
		
		answer = solve(0,0);

		sb.append(answer).append("\n");
		System.out.print(sb);
		
	} // end of main
	/**
	 *solve(y,x) : 시작점(y,x) ~ 오른쪽아래 경로 합 
	 **/
	private static int solve(int y, int x) {
		if(y == map.length-1 && x == map[0].length-1) return 1; // 기저 조건
		if(dp[y][x] != -1) return dp[y][x]; //시작점부터 (y,x)까지의 경로수합 리턴
		
		dp[y][x] = 0;
		for (int k = 0; k < 4; k++) {
			int ny = y + dy[k];
			int nx = x + dx[k];
			if(ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
			if(map[y][x] > map[ny][nx]) {
				dp[y][x] += solve(ny,nx);
			}
		}
		return dp[y][x];
	}

} // end of class