[BOJ] 백준 1520번 내리막 길 (Java)
#1520 내리막 길
난이도 : 골드 4
유형 : DP / DFS
▸ 문제
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.
현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.
지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.
▸ 입력
첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.
▸ 출력
첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.
문제 풀이
본질적으로는 그래프 탐색 문제이다. (0,0)에서 출발하여 (n-1, m-1)로 가는 경우의 수를 모두 구해주면 된다. 이는 최단거리 탐색이 아니라 특정 지점으로의 경우의 수를 구하는 유형이므로 BFS보다는 DFS탐색이 더 유용할 듯 하다.
구상
그러므로 기본 베이스는 DFS탐색으로 잡고 시작하자.
- 그런데 여기서 그래프의 최대 크기는 500x500이다.
이는 재귀호출마다 매번 4방향 탐색을 2500번 하게되니 최악의 경우 엄청난 연산량(4^2500)을 요구한다. 그래서 그냥 DFS탐색만 할 경우 스택에 엄청난 재귀함수가 쌓이면서 메모리초과가 발생할 것이다. 그러므로 DP를 사용하여 중복되는 연산을 제거시켜줘야 한다.
- dp[x][y] = 내리막 길 경우의 수
설계
- (0,0)을 시작점으로 DFS 탐색을 시작한다.
- 4방향을 탐색하며 현재 그래프의 값(pos)보다 작은 그래프의 값(nxt)을 지닌 구역만 탐색한다.
- (n-1, m-1)에 도착하면 1을 카운트해주고 해당 경로는 탐색을 종료한다.
- 방문 여부는 따로 체크해 줄 필요없이 dp값을 0으로 초기화시켜주면서 체크해주면 된다. dp[x][y]=0
- 그러기위해서는 dp값을 -1로 초기화 시켜줘야한다.
- 재귀 탐색이 끝나면 최종적으로 dp[0][0]의 값을 출력해주면 된다. (dfs(0,0) == dp[0][0])
풀이 코드
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int n,m;
static int[][] map, dp;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 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];
dp = new int[n][m];
for (int i = 0; i<n; i++) {
Arrays.fill(dp[i], -1);
}
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(0,0));
}
static int dfs(int x, int y) {
if(x == n-1 && y == m-1) return 1;
if (dp[x][y] != -1) return dp[x][y];
int pos = map[x][y];
dp[x][y] = 0;
for (int i=0; i<4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx <0 || nx > n-1 || ny < 0 || ny > m-1) continue;
int nxt = map[nx][ny];
if (pos > nxt) {
dp[x][y] += dfs(nx, ny);
}
}
return dp[x][y];
}
}