[백준] 1520: 내리막길 (DFS, DP) - JAVA

알고리즘 분류 (dfs)

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

 

 

 

# 문제

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

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

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

 

# 예제

입력 :  첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

4 5
50 45 37 32 30
35 50 40 20 25
30 30 25 17 28
27 24 22 15 10

 

출력 :  첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이

3

 

# 필요개념

그냥 dfs 문제인가 싶었는데 제출하고 보니 시간초과가 발생했다. 그래서 dfs + dp 를 이용하여 문제를 풀었다.

재귀 없이 top-down 방식으로 푸는 방법도 있을텐데 지금 나한텐 어려워서 😇 그냥 재귀로 풀었다!

 

이차원 dp 배열을 만들어서, 해당 위치일 때 가능한 경로개수를 값으로 담아둬서 재사용할 수 있게 하면 시간 초과를 어느정도 막을 수 있다 ! 처음 방문하는 곳이 아니면 해당 값이 들어있을 것이고, 이를 이용해주면 된다. 그래서 dfs 함수 안에 이렇게 코드를 짜주었다. (처음에 dp를 -1로 채워 초기화 해주어서, 그 점을 이용했다)

if (dp[y][x] != -1) return dp[y][x];

 

목적지에 도달하면 1을 리턴하도록 하고, 함수 결과물을 계속 더해나가면 마지막엔 총 경우의 수 개수를 반환하 수 있게 된다. 

 

# Code

import java.io.*;
import java.util.*;
public class Main {
    static int r;
    static int c;
    static int[][] dp;
    static int[][] map;
    static int[] dy = new int[]{0, 1, 0, -1};
    static int[] dx = new int[]{1, 0, -1, 0};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        dp = new int[r][c];
        map = new int[r][c];

        for (int i = 0 ; i < r ; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0 ; j < c ; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = -1;
            }
        }
        int cnt = dfs(0, 0);
        System.out.println(cnt);
    }

    private static int dfs(int y, int x) {
        int height = map[y][x];
        if (y == r - 1 && x == c - 1) {
            return 1;
        }

        if (dp[y][x] != -1) return dp[y][x];

        dp[y][x] = 0;
        for (int i = 0 ; i < 4 ; i++) {
            if (canGo(y + dy[i], x + dx[i], height)) {
                dp[y][x] += dfs(y + dy[i], x + dx[i]);
            }
        }
        return dp[y][x];
    }

    private static boolean canGo(int y, int x, int height) {
        return y >= 0 && y < r && x >= 0 && x < c && map[y][x] < height;
    }
}

 

 

# 결과