[알고리즘] 백준 - 내리막길

백준 - 내리막길

다른 사람 풀이

import sys

sys.setrecursionlimit(10**7)

dx = [-1, 0, 0, 1]
dy = [0, 1, -1, 0]

def dfs(y, x):
    if y == r-1 and x == c-1:
        return 1

    result = 0
    for i in range(4):
        ny, nx = y + dy[i], x + dx[i]
        if 0 <= ny < r and 0 <= nx < c and graph[ny][nx] < graph[y][x]:
            if dp[ny][nx] >= 0:
            # if dp[ny][nx] > 0:
                result += dp[ny][nx]
            else:
                result += dfs(ny, nx)
    dp[y][x] = result
    return result

r, c = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(r)]
dp = [[-1]*c for _ in range(r)]
# dp = [[0]*c for _ in range(r)]
dp[0][0] = 0

print(dfs(0, 0))

예전에도 다른 사람의 풀이를 보고 풀었더니 풀지 못했다. 이번에 확실히 정리하자.

상하좌우에 현재 자신의 위치보다 낮은 지점이 있을 경우, 해당 지점들이 갖는 경로의 수의 합을 현재 위치에 합한다.
한 번 방문해서 경로의 수를 갖고 있다면 그대로 반환하고, 방문한 점이 없던 지점이라면 새롭게 경로의 수를 구한다.

특이한 점은 현재 코드는 통과가 되지만, 코드 밑에 주석들로 대체하면 시간초과가 난다. 이 부분 생각해 보아야 한다.

자바 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class baekjoon_1520 {

    static int R, C;
    static int[][] graph, dp;
    static int[] dx = new int[]{-1, 0, 0, 1};
    static int[] dy = new int[]{0, -1, 1, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        R = Integer.parseInt(inputs[0]);
        C = Integer.parseInt(inputs[1]);
        graph = new int[R][C];
        dp = new int[R][C];

        for (int i = 0; i < R; i++) {
            inputs = br.readLine().split(" ");
            for (int j = 0; j < C; j++) {
                graph[i][j] = Integer.parseInt(inputs[j]);
            }
        }

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                dp[i][j] = -1;
            }
        }
        //dp[i][j] = (i,j)에서 출발하여 (R-1, C-1)까지 가는 방법의 수
        System.out.println(dfs(0, 0));

    }

    private static int dfs(int y, int x) {
        if (y == R - 1 && x == C - 1) {
            return 1;
        }

        int ans = 0;

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (0 <= ny && ny < R && 0 <= nx && nx < C) {
                if (graph[ny][nx] < graph[y][x]) {
                    if (dp[ny][nx] >= 0) {
                        ans += dp[ny][nx];
                    } else {
                        ans += dfs(ny, nx);
                    }
                }
            }
        }
        dp[y][x] = ans;
        return ans;
    }
}