[백준 1520, Java] 내리막 길

문제

www.acmicpc.net/problem/1520

1520번: 내리막 길

 

풀이1- 브루트 포스

 모든 경우의 수를 다 확인해보는 방법이다. 절차는 아래와 같다

1.  현재위치에서 다음위치로 이동한다

2.  이때 다음 위치가 유효한지 확인한다

   1. 다음 위치가 boundary안에 있다

   2. 현재위치보다 다음위치의 높이가 낮다

3. 다음위치로 이동한다

4.  이동한 위치가 도착점(N-1, M-1)이면 count를 1 증가시킨다

하지만 모든 경우의 수를 다 체크하면, 시간 초과가 난다. 

 

가로 N, 세로 M인경우 (0,0)에서 (N-1, M-1)까지 이동하는데 이동하는 칸의 갯수는 N+M-1이다. 이때 한 칸에 대해서 올 수 있는 경우의 수는 4가지 이므로 시간복잡도는 4의 (N+M-1)-2 제곱이된다. N과 M의 최댓값은 500이므로 4의 1000제곱은 10의 600제곱과 근사값이므로 시간초과가 난다

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int M;
    public static int[][] map;
    public static int count = 0;
    public static int[] dx = {-1,0,1,0};
    public static int[] dy = {0,1,0,-1};
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
       
        for(int r = 0 ;r<N; r++){
            st = new StringTokenizer(br.readLine()," ");
            for(int c=0 ;c<M; c++){
                map[r][c] = Integer.parseInt(st.nextToken());
            }
        }
        findPath(0,0);
        int result = count;
        bw.write(String.valueOf(result));
        bw.flush();

        br.close();
        bw.close();

    }
    public static void findPath(int x, int y){
        if(x==N-1 && y ==M-1){
            ++count;
        }
        else {
            for(int d = 0; d<4; d++){
                int nx = x + dx[d];
                int ny = y + dy[d];
                
                if(nx>=0 && ny>=0 && nx<N && ny <M){
                    if(map[nx][ny]< map[x][y]){
                        findPath(nx, ny);
                    }
                }
            }
        }
        
    }
}

 

 

풀이2 - DP

↑ → ↓ ← 순서로 이동한다고 하자.

 

 

(N-1, M-1)에 도착하게되면 파란색부분은 더이상 이동할 수 있는 방향이 없으므로 (0,3)까지 return이 된다. 

 

그러면 다시 (0, 3)에서 ↓으로 호출을 한다. 

 

그런데 여기서 (0, 0) ~ (N-1, M-1)로 가는 첫번째, 두번째 경로에서 중복이 발생하게 된다. 

 초록색으로 표시한 길은 이미 첫번째 경로에서 구했던 경로다. 다시말해 (1, 3)에 도착하면 (3,4) 로 가는 경로는 정해져 있다.  따라서 두번째에서 (3,4)에 도착하면 더이상 탐색을 하지 않아도 된다. 

 

이를 memo[x][y]에 기록을 한다. memo[x][y]은 (x,y)에서 (N-1,M-1)으로 가는 경로의 갯수를 기록해둔다. 이 경우 memo[][]를 -1로 초기화 해서 방문했다/ 방문하지 않았다를 구분해준다. memo[x][y] 가 -1인 경우 이전에 방문한 적이 없기 때문에 (x,y) 에서 (N-1, M-1)로의 경로의 갯수를 구해야한다. 

 

 (x,y) 에서 (N-1, M-1)으로의 경로가 존재하기 위해서는 (x,y)의 이웃 칸인 (nx, ny)에서 (N-1, M-1)까지의 경로가 존재해야한다. 이때 (nx,ny)는 (x,y)의 북, 동, 남, 서 방향에 있고, 범위를 벗어나지 않으며 높이가 (x,y)보다 낮아야 한다. 

 

따라서 memo[x][y] = f(x의 북쪽) + f(x의 동쪽) + f(x의 남쪽) + f(x의 서쪽)  이된다. 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int M;
    public static int[][] map;
    public static int[][] memo;
    public static int count = 0;
    public static int[] dx = {-1,0,1,0};
    public static int[] dy = {0,1,0,-1};
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        memo = new int[N][M];
        for(int r = 0 ;r<N; r++){
            st = new StringTokenizer(br.readLine()," ");
            for(int c=0 ;c<M; c++){
                map[r][c] = Integer.parseInt(st.nextToken());
                memo[r][c] = -1;
            }
        }
        memoPath(0,0);
        int result = memo[0][0];
        bw.write(String.valueOf(result));
        bw.flush();

        br.close();
        bw.close();





    }

    //f(x,y) =  (x,y)에서  (n-1, m-1) 로 가는 경우의 수
    public static int memoPath(int x, int y){
        if(x==N-1 && y==M-1){
            return 1;
        }
        else if(memo[x][y]!=-1){
            return memo[x][y];
        }
        else{
            int count = 0;
            for(int d= 0 ;d<4; d++){
                int nx = x + dx[d];
                int ny = y + dy[d];
                if(nx>=0 && ny>=0 && nx<N && ny<M){
                    if(map[nx][ny]< map[x][y]){
                        count += memoPath(nx, ny);
                    }
                }
            }
            memo[x][y] = count;
            return memo[x][y];
        }
    }
}