백준 1520 내리막길[JAVA]

문제 해석

• 첫번째 줄에 지도의 세로 크기 M과 가로길이 N을 입력받고 두번째 줄부터 MxN개의 각 지점의 높이를 입력받아 이동 가능한 경로의 총 횟수를 구하는 문제이다.

• 문제 풀이 과정은 아래와 같다.
  

• 위에 지도의 각 지점의 높이를 담는 배열과 탐색결과를 정하는 dp배열 총 2개의 배열을 만든다.
  

• 각 지점을 기준으로 움직일 수 있는 방향을 정하는 배열을 만들어 초기화를 해준다.

• 50 => 45 => 37 => 32 => 30 => 25 => 20 => 17 => 15 => 10을 예시로 하나만 작성했다.
  

• 위의 과정으로 기준 지점보다 낮은 높이를 찾아가며 탐색하고, 오른쪽 위부터 왼쪽 아래까지 탐색이 끝나면 시작점(오른쪽 위)에 +1씩 누적합하며 이동 가능한 경로의 총 수를 구한다.

코드

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

public class Main {

    static int N, M;
    static int[][] gis, dp;
    static int[][] move = {{1,0},{-1,0},{0,1},{0,-1}}; //움직이는 방향

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

        M = Integer.parseInt(st.nextToken()); //세로 크기
        N = Integer.parseInt(st.nextToken()); //가로 크기

        gis = 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++){
                gis[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = -1;
            }
        }
        br.close();

        solutionDFS(0, 0); //시작 점은 {0, 0}부터 {M-1, N-1}로 이동하는 것
        System.out.println(dp[0][0]);

    }


    /*파라미터 (탐색하는) x축, y축 값*/
    public static void solutionDFS(int x, int y){
        if(y == (M-1) & x == (N-1)){ //탐색 완료.
            dp[y][x] = 1;
            return;
        }

        if(dp[y][x] != -1) return; //이미 탐색 완료한 경우

        dp[y][x] = 0; //탐색 시작

        for(int[] m : move){
            int nextX = x+m[1]; //이웃한 위치 조회
            int nextY = y+m[0]; //이웃한 위치 조회

            if(nextX < N & nextX >= 0 & nextY < M & nextY >= 0) { //위치 탐색 범위를 벗어나는 것을 방지
                if(gis[y][x] > gis[nextY][nextX]){ //다음 이웃한 위치이면서 현재 탐색한 곳보다 높이가 더 낮은 지점인 경우
                    solutionDFS(nextX, nextY); //다음 위치 탐색
                    dp[y][x] += dp[nextY][nextX]; //dp에 누적 저장
                }
            }
        }


    }
}

결과

느낀 점

문제를 풀고 풀이 과정을 보다보면 이해하고 정리하고 풀 수 있지만 아직 다이나믹 프로그램은 처음부터 문제를 풀어가는 게 어려운 것 같다. 아직 나한테는 너무 어려운 존재,,,