[백준] 1520 내리막 길 (Java)

[1520 내리막 길]

난이도: 골드4

1520번: 내리막 길

문제

입력

출력

---

[아이디어]

처음에는 일반 DFS로 풀었다가 시간 초과가 났다. (다시 생각해보니 대략 500 * 500 * 500 * 500 * 4 정도의 시간이 걸리므로 시간 초과가 나는 것은 당연했다.)

시간 초과가 났기 때문에 DP로 풀어야 하나는 것은 알아챘지만 어떻게 DP를 적용해야 하는지 모르겠어서 구글링을 해봤다.

 

이 분이 설명을 위해 만들어 놓은 애니메이션으로 접근 방법을 알아 차릴 수 있었다.

[백준][1520번][DP] 내리막길

---

[JAVA 코드]

위의 블로그를 통해 이해하고 DP를 적용한 코드

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

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	
	static int N, M;
	static int [][] map;
	static int [][] D;
	static int [] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};
	
	public static void main(String[] args) throws IOException {
		tokens = new StringTokenizer(br.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		
		map = new int [N][M];
		D = new int [N][M];
		for(int r = 0; r < N; r++) {
			tokens = new StringTokenizer(br.readLine());
			for(int c = 0; c < M; c++) {
				map[r][c] = Integer.parseInt(tokens.nextToken());
				D[r][c] = -1; // 초기화
			}
		}
		
		System.out.println(dfs(0, 0));
	}

	private static int dfs(int r, int c) {
		if(r == N - 1 && c == M - 1) return 1;
		if(D[r][c] != -1) return D[r][c];
		
		D[r][c] = 0;
		for(int i = 0; i < 4; i++) {
			int nr = r + dr[i];
			int nc = c + dc[i];
			
			if(nr < 0 || nr >= N || nc < 0 || nc >= M || map[r][c] <= map[nr][nc]) continue;
			
			D[r][c] += dfs(nr, nc);
		}
		
		return D[r][c];
	}

}

 

처음에 시간 초과가 난 일반 dfs 코드

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

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	
	static int N, M, cnt = 0;
	static int [][] map;
	static int [] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};
	
	public static void main(String[] args) throws IOException {
		tokens = new StringTokenizer(br.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		
		map = new int [N][M];
		for(int r = 0; r < N; r++) {
			tokens = new StringTokenizer(br.readLine());
			for(int c = 0; c < M; c++) {
				map[r][c] = Integer.parseInt(tokens.nextToken());
			}
		}
		
		dfs(0, 0);
		
		System.out.println(cnt);
	}

	private static void dfs(int r, int c) {
		if(r == N - 1 && c == M - 1) {
			cnt++;
			return;
		}
		
		for(int i = 0; i < 4; i++) {
			int nr = r + dr[i];
			int nc = c + dc[i];
			
			if(nr < 0 || nr >= N || nc < 0 || nc >= M || map[r][c] <= map[nr][nc]) continue;
			
			dfs(nr, nc);
		}
	}
}