JAVA - 백준 알고리즘 - 1520 내리막길

이 문제는 dp를 사용하여 풀 수 있는 문제이다. 

dp를 사용하는데 완전히 익숙해지지 않았는지 계속 시간초과가 났다.

2시간정도 시도 해보다가 결국 다른 블로그에서 코드를 참고하여 테스트케이스를 디버깅해보고 문제를 해결했다.

 

(왼쪽 오른쪽 위쪽 아래쪽)으로 움직여야 할때 nx와 ny를 사용해 간단하게 표현하는 테크닉에 익숙해지도록 자주 사용해봐야 겠다.

 

자세한 설명은 주석을 참고하면 좋을 것 같다.

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

public class P1520 {

	static int[][] map;
	static int[][] dp;
	static int row;
	static int col;
	static int[] nx = { -1, 0, 1, 0 };
	static int[] ny = { 0, 1, 0, -1 };  // 위쪽 오른쪽 아래쪽 왼쪽

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		row = Integer.parseInt(st.nextToken());
		col = Integer.parseInt(st.nextToken());
		map = new int[row][col];
		dp = new int[row][col];

		for (int i = 0; i < row; i++) {
			StringTokenizer st2 = new StringTokenizer(br.readLine());
			for (int j = 0; j < col; j++) {
				map[i][j] = Integer.parseInt(st2.nextToken());
				dp[i][j] = -1;
			}
		}		// 입력  dp에 -1로 초기화해주는 이유는 방문한 곳인지 체크하기 위해서.
		System.out.println(cntMiro(0,0));
	}

	public static int cntMiro(int x, int y) {
		if (x == row - 1 && y == col - 1)
			return 1;		//  끝 블록에 도달하면 1 return
		if (dp[x][y] != -1)
			return dp[x][y];	//	이미 도달한 블럭이면 return

		dp[x][y] = 0;			// 방문한 블럭 표시

		for (int i = 0; i < 4; i++) {		// 위 오른쪽 아래 왼쪽 돌아가며 확인
			int tmpx = x + nx[i];
			int tmpy = y + ny[i];

			if (tmpx < row && tmpy < col && tmpx >= 0 && tmpy >= 0)  // index out of range 방지
				if (map[x][y] > map[tmpx][tmpy])	// 내리막
					dp[x][y] += cntMiro(tmpx, tmpy);	// 내리막으로 진행된 경로에 전부 +1
		}

		return dp[x][y];
	}

}