[BOJ/Java] 1520. 내리막 길

[BOJ/Java] 1520. 내리막 길

1520번: 내리막 길

---

문제 해석

"내리막 길" 문제는 지정된 MxN 격자에서 각 셀에는 높이가 주어지며, 항상 상하좌우로만 이동할 수 있는 조건에서, 시작점 (M, N)에서 목표점 (1, 1)까지 내리막길로만 이동하는 경로의 수를 구하는 문제이다. 이동은 오직 더 낮은 높이의 셀로만 가능하다.

풀이 과정

이 문제는 동적 프로그래밍(DP)과 깊이 우선 탐색(DFS)을 활용하여 해결할 수 있다. DP 배열 dp를 사용하여 각 위치에서 목표 위치까지 도달 가능한 경로의 수를 메모이제이션하며, 초기값으로 -1을 설정하여 아직 계산되지 않은 상태를 나타낸다. DFS를 통해 모든 가능한 경로를 탐색하면서 dp 값을 갱신해 나간다. 각 위치에서는 상하좌우로 이동 가능하지만, 높이가 높은 셀로는 이동할 수 없다는 조건이 있어 이를 검사하는 로직을 추가한다.

코드

package edu.ssafy.im.BOJ.Gold.G3.No1520;

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

public class Main {
    private static int M, N;
    private static int[][] map, dp;
    private final static int[][] direction = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        map = new int[M][N];
        dp = new int[M][N];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken()); // 지도 입력 받기
                dp[i][j] = -1; // 미방문 시 -1로 초기화
            }
        }

        dfs(M-1, N-1); // 목표지점에서 시작하여 경로 탐색

        sb.append(dp[M-1][N-1]);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static int dfs(int x, int y) {
        if (x == 0 && y == 0) return 1; // 출발지 도달 시 이동 가능한 경로 수는 1

        if (dp[x][y] != -1) return dp[x][y]; // 이미 계산된 위치라면 저장된 값 반환

        dp[x][y] = 0; // 방문 처리 및 경로 수 초기화
        for (int[] d : direction) {
            int nx = x + d[0];
            int ny = y + d[1];

            if (nx < 0 || ny < 0 || nx >= M || ny >= N || map[nx][ny] >= map[x][y]) continue; // 범위 밖 이동과 높이 조건 검사

            dp[x][y] += dfs(nx, ny); // 재귀적으로 경로 수 계산 및 덧셈
        }

        return dp[x][y];
    }
}

시간 복잡도 분석

각 위치마다 한 번씩만 탐색을 진행하며, 상하좌우 네 방향을 검사하는 경우는 상수 시간에 해당한다. 따라서 전체적인 시간 복잡도는 O(MN)이다.

느낀점

동적 프로그래밍과 깊이 우선 탐색을 결합하여 문제를 해결하는 방식은 종종 복잡한 문제에 대해 효과적인 접근 방식을 제공한다. 특히, 메모이제이션을 활용함으로써 중복 계산을 방지하고, 실행 시간을 크게 단축시킬 수 있다는 것을 재확인할 수 있었다. 이러한 접근 방식은 앞으로도 다양한 문제에 적용 가능할 것으로 기대된다.