[백준 / BOJ] 1520번 : 내리막길 - JAVA

https://www.acmicpc.net/problem/1520

1520번: 내리막 길

DFS + 다이나믹 프로그래밍

어떤 한 좌표 (i, j)에 도달할 수 있는 경우의 수는, 주변 4방향 중 (i, j)보다 높은 곳에 도달할 수 있는 경우의 수의 합과 같다. 문제에서는 내리막길을 사용해서 (N, M)에 도달해야 한다고 적혀 있는데, 이는 반대로 말한다면 (N, M)부터 (1, 1)까지는 오르막길이라는 뜻이다. 이에 따라 다음과 같은 DFS 함수를 선언했다.

 

private static int dfs(int r, int c) {
		
    if(v[r][c]) return cost[r][c];

    int cnt = 0;
    for (int d = 0; d < 4; d++) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if(nr >= N || nc >= M || nr < 0 || nc < 0 || map[nr][nc] <= map[r][c]) continue;
        cnt += dfs(nr, nc);
    }
    v[r][c] = true;
    return cost[r][c] = cnt;
}

 

이미 방문한 적이 있다면, 해당 위치에 도달할 수 있는 경우의 수를 리턴한다. 방문한 적이 없다면 네 방향을 살펴보면서 현재 위치보다 높은 곳의 경우의 수를 더해준다.

 

이때 경우의 수와 방문 체크 배열을 따로 둔 것은 방문한 적이 있더라도 주변이 모두 현재 위치보다 낮아 cost[r][c]가 0 (초기값)으로 계속 남아있을 수도 있기 때문이다. 처음에는 방문 체크 배열을 따로 두지 않고 cost[r][c] > 0인 경우에 return하도록 했는데, 이렇게 하니 시간 초과가 나왔다. 방문 배열 v를 따로 선언하자 맞출 수 있었다.

 

전체 코드

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

// 시간 : 308ms
// 메모리 : 38832KB
public class Main {

	static int N;
	static int M;
	static int[][] map;
	static int[][] cost;
	static boolean[][] v;
	static int[] dr = {-1,0,1,0};
	static int[] dc = {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());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new int[N][M];
		cost = new int[N][M];
		v = new boolean[N][M];
		cost[0][0] = 1;
		v[0][0] = true;
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		System.out.println(dfs(N - 1, M - 1));
	}
	
	private static int dfs(int r, int c) {
		
		if(v[r][c]) return cost[r][c];
		
		int cnt = 0;
		for (int d = 0; d < 4; d++) {
			int nr = r + dr[d];
			int nc = c + dc[d];
			if(nr >= N || nc >= M || nr < 0 || nc < 0 || map[nr][nc] <= map[r][c]) continue;
			cnt += dfs(nr, nc);
		}
		v[r][c] = true;
		return cost[r][c] = cnt;
	}

}