[백준 알고리즘] 1520번 자바(Java) 내리막길

조건

문제

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

  

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

 

출력

첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.

 

풀이

M과 N이 최대 500자연수이다. 따라서 map은 500x500인 25만이 되고 그렇다보니 시간복잡도가

O(n^2)이 아닌 O(n log n)방법을 찾아야한다. 따라서 처음에 생각한 dfs(깊이 우선 탐색)은 시간초과가 날 수 밖에 없다. 다음으로 생각한 방법은 dp를 생각해서 입력받을때마다 상하좌우의 값을 비교하여 이동가능한 경우를 계속 추가하여 map[m-1][n-1]에 가능한 경로의수를 모두 저장하는 방법을 생각하였다. 하지만 이 처음 생각한 dp는 화살표가 2단으로 이전으로 돌아갈 경우 다시 값을 체크 못하는 문제점이 있었다. 

 

이런 과정을 거치고 최종적으로 생각한 방법은 m,n 칸에 도달하면 return 1을 주는 식으로 하고 각 칸은 상하좌우에 있는 본인보다 작은 값을 가진 칸의 경우의 수를 합하는 식으로 진행을 했다. 아래 그림을 통해 설명하겠다.

 

 

과정 1

과정 2

시작은 (1,1)에서 시작해서 해당칸보다 작은 칸에 계속 들어가며 식을 수행하는 재귀 형식으로 진행된다. 

그렇게 해서 (m,n)에 도달하게 되면 return 1을 하게되는거고 그 과정부터가 이제 그림으로 나타나있다. 

(m,n)까지 도달하는 과정은 아래 코드를 보면 이해가 쉽게 될것 같다.

 

 

예제 입력 예시

4 5
50 45 37 32 30
35 50 40 20 25
30 30 25 17 28
27 24 22 15 10

 

예제 출력 예시

3

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//1520번 내리막 길

public class Main {
    static private int m;
    static private int n;
    static private int[][] map;
    static private int[][] arr;
    static private int[][] xy ={{0,-1},{-1,0},{0,1},{1,0}};

    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());
        map = new int[m][n];
        arr = 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());
                arr[i][j] = -1;
            }
        }

        System.out.println(bfs(0,0));
    }

    static int bfs(int y, int x){
        if(y==m-1&&x==n-1){
            return 1;
        }
        else if(arr[y][x]!=-1){
            return arr[y][x];
        }
        else{
            arr[y][x] = 0;
            for (int i = 0; i < 4; i++) {
                //작으면 bfs들어가고 리턴값 얻기, 크면 암것도 없음
                int curY = y+xy[i][0];
                int curX = x+xy[i][1];
                if(curY>=0&&curY<m&&curX>=0&&curX<n&&map[y][x]>map[curY][curX]){
                    arr[y][x]+=bfs(curY, curX);
                }
            }
            //System.out.println("y: "+y+"x: "+x+" 값: "+map[y][x]+"경우의 수:"+arr[y][x]);
            return arr[y][x];
        }
    }
}

 

 

 

문제 출처

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

1520번: 내리막 길