[JAVA]백준 1520번: 내리막 길

www.acmicpc.net/problem/1520

1520번: 내리막 길

 

1. 문제 설명

 

지도가 있을 때 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 문제이다.

 

list 배열로 지도를 입력받고 list 배열과 같은 크기의 cache 배열을 만들고 -1로 채운다.

 

-1로 채우는 이유는 현재 위치를 방문했는지 방문하지 않았는지 구분하기 위해서이다.

 

그 후 재귀를 통해 현재 위치와 각각의 상, 하, 좌, 우 list 값을 비교해 다음 위치의 크기가 더 작다면 다음 위치로 이동한다.

 

시간복잡도는 O(NM)이다.

 

2. 코드

 

import java.awt.image.BufferedImageFilter;
import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static int height,width;
    public static int target;

    public static int[][] list=new int[501][501];

    public static int[][] cache=new int[501][501];

    public static int[][] plus={{0,1},{0,-1},{1,0},{-1,0}};


    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);

        height=scan.nextInt();
        width=scan.nextInt();

        for (int x = 0; x < height; x++) {
            for (int y = 0; y < width; y++) {
                list[x][y] = scan.nextInt();
                cache[x][y] = -1;
            }
        }

        System.out.println(make_route(0,0));



        scan.close();


    }

    public static int make_route(int now_x,int now_y){

        if (now_x == height - 1 && now_y == width - 1) {
            return 1;
        }

        if(cache[now_x][now_y]!=-1)
            return cache[now_x][now_y];

        int ret=0;

        for(int index=0;index<4;index++){

            int next_x=plus[index][0]+now_x;
            int next_y=plus[index][1]+now_y;
            if (isRange(next_x, next_y) && list[next_x][next_y] < list[now_x][now_y]) {
                ret+=make_route(next_x,next_y);
            }
        }

        cache[now_x][now_y]=ret;

        return ret;

    }

    public static boolean isRange(int x,int y){
        if(x>=height || y>=width || x<0 || y<0)
            return false;
        return true;
    }

}