[백준 자바 1520] 내리막 길 (골드3)

 

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

 

 

설명

처음에는 BFS로 풀었다. 근데 BFS로 노드를 지나가면서 방문 체크를 해두는데, 이미 방문한 노드에 대해서는 이후 다른 경로에서는 거치지 않기 때문에 경로가 딱 1개만 나왔다. 그렇다고 지나간 경로를 체크 안 하면 무한 루프에 빠져서 BFS는 버렸다. 

 

그 다음에는 DFS로 풀었다. 답은 나왔는데, 시간 초과가 떴다. 

 

그래서 곰곰이 생각하다가 DP로 풀었더니 풀렸다. 

 

탑다운 방식으로 풀었다.

범위를 벗어나는 좌표에서는 0을 리턴하고, 

이미 계산한 좌표에서는 그대로 계산 값을 리턴하고, 

아직 계산하지 않는 좌표에 대해서는 현재 좌표의 상하좌우의 높이를 비교해서 현재 높이보다 큰 인접 좌표에 대해서 재귀로 dp를 호출했다. 

 

static int N, M;
static int[][] graph;
static Integer[][] dp;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};

 

이번에 쓰일 변수들이다. 

문제에서는 N은 가로길이, M은 세로길이로 했지만 나는 N이 세로길이인 것이 편해서 반대로 했다. 

또 각 좌표의 높이값을 담은 graph,

경로 수를 저장할 dp를 두었다. 원래 참조타입으로는 배열을 안 쓰는데 아직 계산을 하지 않아 비었다는 null을 사용하고자 이번에는 썼다. 

그다음 상하좌우를 편리하게 쓸 dx, dy를 두었다. 

 

 

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());

N = stoi(st.nextToken());
M = stoi(st.nextToken());

graph = new int[N][M];
dp = new Integer[N][M];
dp[0][0] = 1;

for (int i = 0; i < N; i++) {
    st = new StringTokenizer(br.readLine());
    for (int j = 0; j < M; j++) {
        graph[i][j] = stoi(st.nextToken());
    }
}

 

그 다음 입력부. 

stoi는 Integer.parseInt(String s) 함수를 더 쓰기 편하게 따로 함수화 해둔거다. 

그리고 dp[0][0] = 1을 해주어 시작 경로 1개를 입력해두었다. 

그 밑은 각 좌표의 높이값을 입력해주는 이중 for문. 

 

 

 

static int dp(int x, int y) {
    if (x < 0 || x >= N || y < 0 || y >= M) {
        return 0;
    }

    if (dp[x][y] != null) {
        return dp[x][y];
    }

    dp[x][y] = 0;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if ((0 <= nx && nx < N) && (0 <= ny && ny < M) && (graph[x][y] < graph[nx][ny])) {
            dp[x][y] += dp(nx, ny);
        }
    }

    return dp[x][y];
}

 

아까 위에서 설명했듯, 

범위를 벗어나는 좌표는 0을 리턴하고, 

이미 계산하여 null이 아니면 그 값을 리턴한다. 

 

그 이후로 우선 좌표값이 null이므로 0으로 입력을 해준 뒤,

상하좌우를 돌면서 만약 범위를 안 벗어나면서 현재 높이보다 높은 인접좌표가 있다면 그 좌표의 경로 수를 가져와서 더해주도록 for문을 구성했다. 

 

마지막으로 계산한 dp값을 리턴한다. 

 

 

끝!

 

 

 

 

 

 

전체 코드 

import java.io.*;
import java.util.*;

public class Main {
    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    static int N, M;
    static int[][] graph;
    static Integer[][] 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 = stoi(st.nextToken());
        M = stoi(st.nextToken());

        graph = new int[N][M];
        dp = new Integer[N][M];
        dp[0][0] = 1;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                graph[i][j] = stoi(st.nextToken());
            }
        }

        System.out.println(dp(N - 1, M - 1));
    }

    static int dp(int x, int y) {
        if (x < 0 || x >= N || y < 0 || y >= M) {
            return 0;
        }

        if (dp[x][y] != null) {
            return dp[x][y];
        }

        dp[x][y] = 0;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if ((0 <= nx && nx < N) && (0 <= ny && ny < M) && (graph[x][y] < graph[nx][ny])) {
                dp[x][y] += dp(nx, ny);
            }
        }

        return dp[x][y];
    }
}