백준 1520 - 내리막 길

Java

1520 번 - 내리막 길

문제

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다.
한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다.
그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

접근 방법

DFS를 사용하면 0,0에서 시작하여 n-1, m-1까지 도착하는 개수의 수가 즉 경로의 개수이다.
하지만, 단순하게 DFS를 사용하면 시간초과가 나므로, DP를 이용하여 시간을 단축한다.

DP의 방법은, 이미 방문한 지점을 다른 경로가 그 지점을 방문하려 할 때, 방문하는 것 대신 현재 그 지점의 경로의 개수를 받아오는 것이다.

위는 간단한 예제이다.
노란 선의 경로로 목표인 1 지점까지 이동하였으면, 해당 지점의 DP값은 1이다.
이후 초록 선의 경로가 1 지점에 도달하려했지만, 해당 지점은 이미 방문 하였으므로, 해당 DP값을 리턴한다.
해당 DP는 1이므로 1 + 1로 경로는 총 2개가 된다.

위를 반복하면, 0,0 시작점에는 각 경로들이 리턴되며 그것들의 합이 총 경로의 수가 된다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, m, result;
	static long cnt = 0;
	static int[][] map, dp;
	static boolean[][] vis;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());
    	
    	map = new int[n][m];
    	dp = new int[n][m];
    	
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < m; j++) {
    			map[i][j] = stoi(stk.nextToken());
    			dp[i][j] = -1;		// 초기 상태는 -1로 한다.
    		}
    	}

    	System.out.println(dfs(0,0));
    	br.close();
	}
	// 하, 우, 상, 좌
	static int[] dy = {1,0,-1,0};
	static int[] dx = {0,1,0,-1};
	
	static int dfs(int y, int x) {
		if(y == n - 1 && x == m - 1) {
			return 1;
		}
		
		// 이미 한번 방문한 지점이면 해당 값을 리턴하고 종료한다.
		if(dp[y][x] != -1)
			return dp[y][x];
		
		dp[y][x] = 0;
		
		int ny,nx;
		for(int i = 0; i < 4; i++) {
			ny = y + dy[i];
			nx = x + dx[i];
			
			if(isIn(ny,nx) && map[y][x] > map[ny][nx]) {
				dp[y][x] += dfs(ny,nx);		// 경로 수를 추가한다.
			}
		}
		return dp[y][x];
	}
	
    // 주어진 범위 안에 있는가
    public static boolean isIn(int y, int x){
        if(y < 0 || y >= n || x < 0 || x >= m)
            return false;
        return true;
    }
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

시작점의 값으로 dp가 모이는 하향식의 문제였다.

개선할 점

없습니다.