📙[Algo] 24.03.11 알고리즘

알고리즘 문제) BOJ 1520. 내리막 길

• 링크 : https://www.acmicpc.net/problem/1520

문제 요약

• 여러 칸으로 나뉜 지도가 있음
• 각 칸은 지점을 나타내며, 지점의 높이가 쓰여있다
• 지점끼리는 상하좌우 이동 가능
• 세준이 처음 위치 : (0,0)
• 목적지 : 맨 오른쪽 아래 칸
• 항상 높이가 더 낮은 지점으로만 이동
• 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수 구하기

시간 제한

• 2초

입력

• 지도 세로 크기 M, 가로 크기 N
• M개의 줄에 N개씩 지점의 높이가 주어짐
  • M과 N은 500이하 자연수
  • 각 지점 높이는 10000이하 자연수

출력

• 이동 가능한 경로의 수 H 출력
  • 10억 이하의 음이 아닌 정수

접근법

1. 백트랙킹으로 생각하기
   • 상하좌우를 살펴 내리막길로 갈 수 있는 경우를 탐색
   • recur(int row, int col, int height)
   • 이때, row와 col이 M-1, N-1 인 경우에 대해서 카운팅
   • 만약 이전 지점의 height와 현재 높이를 비교하여 내리막길이 아닌경우

코드

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

public class Main {
    static int M, N;
    static int[][] arr;
    static int[] delR = {-1, 1, 0, 0};
    static int[] delC = {0, 0, -1, 1};
    static int[][] dp;
//    static int answer;

    // 1. 백트랙킹으로 풀기
//    static void recur(int row, int col, int height) {
//
//        if (height <= arr[row][col]) return;
//
//        if (row == M - 1 && col == N - 1) {
//            answer++;
//            return;
//        }
//
//        int mrow, mcol;
//        for (int i = 0; i < 4; i++) {
//            mrow = row + delR[i];
//            mcol = col + delC[i];
//
//            if (mrow < 0 || mcol < 0 || M <= mrow || N <= mcol) continue;
//
//            recur(mrow, mcol, arr[row][col]);
//        }
//
//    }

    // 2. 함수 + 메모이제이션 적용
    static int recur(int row, int col, int height) {

        if (height <= arr[row][col]) return 0;

        if (row == M - 1 && col == N - 1) return 1;

        if (dp[row][col] != -1) return dp[row][col];

        int mrow, mcol;
        int ret = 0;
        for (int i = 0; i < 4; i++) {
            mrow = row + delR[i];
            mcol = col + delC[i];

            if (mrow < 0 || mcol < 0 || M <= mrow || N <= mcol) continue;

            ret += recur(mrow, mcol, arr[row][col]);
        }

        dp[row][col] = ret;
        return dp[row][col];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

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

        dp = new int[M + 1][N + 1];

        for (int i = 0; i < M + 1; i++) {
            Arrays.fill(dp[i], -1);
        }

//        recur(0,0, 10010);

//        bw.write(String.valueOf(answer));
        bw.write(String.valueOf(recur(0,0,10001)));
        bw.flush();
        bw.close();
        br.close();
    }
}