백준 1520번 : 내리막 길

1. 문제 설명 (1520)

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



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



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

2. 분류

• DP
• DFS
  
  

3. 풀이

무지성으로 DFS만으로 풀다가 끔찍한 결과와 마주했다.

문제의 조건에서 세로, 가로의 크기 M, N <= 500, 높이 <= 10000 라는 조건이 있었는데,
M = 500, N = 500, 높이 = 10000 일 경우 (끔찍한 시간 초과) 가 발생한다는 점을 간과했다.

그래서 DFS와 DP를 같이 사용해야 했다.
이미 탐색한 경로에 대해서 메모이제이션을 진행했다.
DP 배열을 “-1” 로 초기화함으로써 경로의 수가 없는 경우 와 아직 탐색을 하지 않은 경우 를 구별해주었다.

Test Case의 input으로 구해진 DP 배열은 다음과 같다.

3	2	2	2	1
1	-1	-1	1	1
1	-1	-1	1	-1
1	1	1	1	0

dfs 메소드는 DP[1, 1]값인 “3”을 return 한다.

4. 코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

import java.io.*;   public class Q1520 {       static int[][] map;     static int[][] dp;     static int M, N;          public static void main(String[] args) throws IOException{         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         String[] temp = br.readLine().split(" ");         M = Integer.parseInt(temp[0]);         N = Integer.parseInt(temp[1]);         map = new int[M+1][N+1];         dp = new int[M+1][N+1];                  for(int i = 1; i <= M; i++) {             String[] num = br.readLine().split(" ");             for(int j = 1; j <= N; j++) {                 map[i][j] = Integer.parseInt(num[j-1]);                 dp[i][j] = -1;             }         }                  int answer = dfs(1, 1);         bw.write(answer+"");         bw.flush();         bw.close();     }          static int dx[] = {0,0,1,-1};     static int dy[] = {1,-1,0,0};          private static int dfs(int x, int 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 && ny > 0 && nx <= M && ny <= N){                 if(map[nx][ny] < map[x][y]) {                                          if(nx == M && ny == N)                         dp[x][y] += 1;                     if(dp[nx][ny] >= 0)                          dp[x][y] += dp[nx][ny];                     else                         dp[x][y] += dfs(nx, ny);                 }             }         }         return dp[x][y];     }      } Colored by Color Scripter

cs

5. 결과

432ms로 잘 작동한다.