[java] 백준 알고리즘 1520번 내리막 길 풀이

memoization을 활용한 문제다. 

동적계획법에 나오는 유형이라는데 memoization이라는 개념은 이 문제를 풀면서 알게 됐다.

재귀개념까지만 알아서 재귀로 푸니 시간초과.

역시 재귀만 해서는 시간이 많이 걸린다.

원래 계산했던 것을 기억해두고 이전에 했던 계산을 다시 꺼내 줌으로써 반복계산을 피하는 방법이

memoization을 사용하는 방법이다.

이 문제는 이전에 방문했는지를 체크해줄 필요가 없다. 

내리막길로 이동한 순간, 다시 오르막으로 올 일이 없기 때문에 이전에 방문했던 곳을 다시 방문할 일이 없다.

if문에서 현재 값보다 다음 값이 작아야만 이동하게 만들 것이기 때문에.

* 풀이 소스

public class Baekjoon1520 {
 
    static int vertical; // 가로(행)
    static int horizontal; // 세로(렬)
    static int[][] map; // 지도
    static int[][] memoization; // 메모이제이션
    
    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 = new StringTokenizer(br.readLine());
        
        vertical = Integer.parseInt(st.nextToken()); 
        horizontal = Integer.parseInt(st.nextToken());
        map = new int[vertical][horizontal];
        memoization = new int[vertical][horizontal];
        
        for(int i=0; i<vertical; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<horizontal; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                memoization[i][j] = -1;
            }
        }
        
        bw.write(String.valueOf(findWay(0,0)));
        bw.flush();
    
    }    
    
    private static int findWay(int x, int y) {
        
        if(x == vertical-1 && y == horizontal-1) { // 도착지점에 도달하면 경로의 수 1을 리턴한다
            return 1;
        }
        
        if(memoization[x][y] == -1) { // 경로의 수가 계산된 적 없고, 방문한 적 없는 경우만 계산
            memoization[x][y] = 0;
            
            // 위로 이동
            if(x > 0 && map[x][y] > map[x-1][y]) {
                memoization[x][y] += findWay(x-1, y);
            }
            // 아래로 이동
            if(x < vertical-1 && map[x][y] > map[x+1][y]) {
                memoization[x][y] += findWay(x+1, y);
            }
            // 왼쪽으로 이동
            if(y > 0 && map[x][y] > map[x][y-1]) {
                memoization[x][y] += findWay(x, y-1);
            }
            // 오른쪽으로 이동
            if(y < horizontal-1 && map[x][y] > map[x][y+1]) {
                memoization[x][y] += findWay(x, y+1);
            }
        }
        return memoization[x][y]; // 이미 와봤던 경로라면 계산된 경로의 수를 return
        
    }    
}

 

Colored by Color Scriptcs

if문의 중복을 줄일 수도 있겠지만, 가독성 면에서는 이게 더 좋지 않을까 싶어 이렇게 짰다.

예시로 나온 

4 5

50 45 37 32 30

35 50 40 20 25

30 30 25 17 28

27 24 22 15 10

을 입력하면, 계산된 memoization 결과 값은 아래와 같이 나온다.