[알고리즘 문제풀이] 백준 1520 내리막 길

프로그래머스 고득점 kit를 다 풀어서 tony9402님의 백준 문제집을 풀기로 결정했다 ! 이제는 너무 쉬운 문제부터 순차적으로 풀기도 좀 그렇고 해서 랜덤하게 풀기 위해서 저 문제집에서 카테고리와 문제를 랜덤하게 뽑아주는 프로그램을 만들어서 뽑아주는 문제를 풀기로 했다 !

그래서 오늘 푼 문제는 백준 1520번 내리막 길이라는 문제이다. ( 문제링크 )

문제

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

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

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

입력

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

출력

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

예제

입력

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

출력

3

풀이 방법

아니 백준은 너무 오랜만에 풀어서 클래스가 Main이어야 하는 것도 몰랐었다.. 그리고 입출력을 그냥 System.in System.out으로 했더니 통과는 하는데 시간 + 메모리가 다른 사람에 비해서 엄청나게 나오는 것이다.. 그래서 다른 분들 코드 보고 입출력 방법을 바꿨다 ㅎㅎ 간만이니까 ~~

1. DFS + DP

시작점인 [0,0]부터 재귀로 DFS로 탐색을 시작한다. 이 때, dp배열에는 [x,y]로부터 도착점까지 경로의 수가 저장된다. dp 초기화는 -1로 해주었고, 방문한 경우에는 경로의 수가 저장되는 것이다. ( 해당 좌표로부터 도착점까지 갈 수 있는 경로가 없다면 0이 저장된다. 방문은 하였으나 경로는 없는 ! 그래서 초기화는 -1로 해주었다. )

이 과정은 시작점부터 사방을 순차적으로 이동하며 탐색하는데 ( 배열 범위를 벗어나는 것은 체크해준다! ) 다음 이동할 좌표의 값이 현재 좌표의 값보다 크다면 이동할 수 있는 점이므로 재귀 방문을 해준다. dfs함수의 반환값은 현재 좌표의 dp값이다. 반환하며 함수가 종료되면, 이 반환된 좌표의 유입지점의 dp값에 이 값이 더해진다. 이 때, 도착점인 [m,n]는 도착점이므로 1을 반환해준다. 또한 방문할 지점이 다른 경로로 이미 방문한 점이라면, 즉 -1이 아니라면 그 점으로부터 도착지까지의 경로는 이미 저장되어 있는 것이므로 탐색 반복할 필요 없이 이미 저장된 값을 반환해주어 dp에 더해지게 해주면 된다 !

2. BFS + DP

BFS로 탐색하는 방법 역시 dp는 똑같이 [x,y]로부터 도착점까지의 경로가 저장된다. 다만 탐색이 BFS방식으로 진행된다. [0,0]부터 현재 좌표의 사방을 탐색하며, 좌표를 벗어나지 않고 현재 좌표에 저장된 값보다 큰 값이 저장되어 있다면 다음 좌표가 될 수 있으므로, 현재 좌표까지의 경로 수 즉 dp에 저장된 값을 다음 좌표의 dp에 더해준다.

이 때, [x1,y1]의 dp값을 반영하여 [x2,y2]의 값을 설정한 후에 [x1,y1]에 다시 방문할 수 있게 되어 다시 값이 갱신될 수 있는 경우가 생긴다. 위의 예시에서 동서남북 순서로 사방을 탐색한다면 아래의 그림에서 초록 하이라이트 부분이 먼저 반영되고, 노란 하이라이트가 반영되면서 노란 하이라이트의 경로가 [2,3]에 반영이되지 않는 것이다 !!!!

이 문제를 해결하기 위하여 높은 값에서 낮은 값으로만 이동할 수 있다는 성질을 이용하여 PriorityQueue를 이용하여 좌표에 저장된 값의 내림차순으로 큐에 들어가게 해주었다. 그러면 현재 방문할 수 있는 좌표 후보들, 즉 큐에 저장된 좌표들 중에서 큰 값을 가진 좌표 순으로 탐색하게 되는 것이고, 현 좌표의 값보다 큰 값을 가진 좌표는 이미 다 방문한 것이 된다 ! 즉 현 좌표까지 올 수 있는 가능성이 있는 모든 좌표의 값이 반영되는 것이다

위의 탐색 과정은 큐가 빌 때까지 큐에서 좌표를 하나씩 꺼내어 그 좌표를 현재 좌표로 갱신하며 반복하여 탐색을 진행해주면 된다.

코드

1. DFS + DP

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

public class Main {
    public static int[] dx = {0, 0, 1, -1};
    public static int[] dy = {1, -1, 0, 0};
    public static int m;
    public static int n;
    public static int[][] graph;
    public static int[][] dp;

    public static int dfs(int x, int y){
        if(x==m && y==n) return 1;
        if(dp[x][y]!=-1) return dp[x][y];
        dp[x][y] = 0;
        int nextX, nextY;
        for(int i=0; i<4; i++){
            nextX = x+dx[i];
            nextY = y+dy[i];
            if(nextX < 0 || nextX > m || nextY < 0 || nextY > n) continue;
            if(graph[nextX][nextY] < graph[x][y]){
                dp[x][y] += dfs(nextX, nextY);
            }
        }
        return dp[x][y];
    }

    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());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        graph = 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++){
                graph[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = -1;
            }
        }
        m--; n--;
        bw.write(dfs(0, 0) + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

2. BFS + DP

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

public class Main {
    public static int[] dx = {0, 0, 1, -1};
    public static int[] dy = {1, -1, 0, 0};

    public static int bfs(int[][] graph, int[][]dp){
        int m = graph.length-1;
        int n = graph[0].length-1;
        int[] current;
        int nextX, nextY, curX, curY;
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return graph[o2[0]][o2[1]] - graph[o1[0]][o1[1]];
            }
        });
        queue.add(new int[]{0, 0});
        dp[0][0] = 1;
        while(!queue.isEmpty()){
            current = queue.poll();
            curX = current[0];
            curY = current[1];
            for(int k=0; k<4; k++){
                nextX = curX+dx[k];
                nextY = curY+dy[k];
                if(nextX < 0 || nextX > m || nextY < 0 || nextY > n) continue;
                if(graph[nextX][nextY] < graph[curX][curY]){
                    if(dp[nextX][nextY] == 0) queue.add(new int[]{nextX, nextY});
                    dp[nextX][nextY] += dp[curX][curY];
                }
            }
        }
        return dp[m][n];
    }

    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());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        int[][] graph = new int[m][n];
        int[][] dp = new int[m][n];
        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++){
                graph[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = 0;
            }
        }
        bw.write(bfs(graph, dp) + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}