• 백준 1520번 내리막 길 :: 마이구미
    알고리즘 풀이/동적계획법 2017. 10. 12. 09:35
    반응형

    이 글은 백준 알고리즘 문제 1520번 "내리막 길" 을 풀이한다.

    풀이 방법은 DFS + DP(동적계획법) 을 통해 해결한다.

    DFS - http://mygumi.tistory.com/102

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



    단순히 모든 경로를 탐색한다면, 시간 초과를 경험하게 된다.

    시간을 줄일 수 있는 방법은 다음과 같다.

    20 지점에 오면 더이상 탐색할 필요가 없이 경로가 존재한다는 것을 찾을 수 있다.

    존재하는 경로를 활용하는 방법으로써, 동적계획법을 이용할 수 있다.


    dp[y][x] = (y, x) 지점일 때 존재하는 경로의 갯수


    DFS를 완벽히 이해하고 있다면, 쉽게 코드를 이해할 수 있다.

    * dp배열을 -1로 초기화한 이유는 방문여부를 위함이다.


    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
    static int[] dx = { -101};
    static int[] dy = { 0-10};
    static int[][] map, dp;
    static int m, n;
     
    private void solve() {
        m = sc.nextInt();
        n = sc.nextInt();
        map = new int[m][n];
        dp = new int[m][n];
     
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                map[i][j] = sc.nextInt();
                dp[i][j] = -1;
            }
        }
        System.out.println(dfs(m - 1, n - 1));
    }
     
    public static int dfs(int y, int x) {
        if (y == && x == 0) {
            return 1;
        }
     
        if (dp[y][x] == -1) {
            dp[y][x] = 0;
            for (int i = 0; i < 4; i++) {
                int nx = dx[i] + x;
                int ny = dy[i] + y;
     
                if (<= nx && nx < n && <= ny && ny < m) {
                    if (map[y][x] < map[ny][nx]) {
                        dp[y][x] += dfs(ny, nx);
                    }
                }
            }
        }
        return dp[y][x];
    }
    cs


    반응형

    댓글

Designed by Tistory.