[백준 JAVA] 1520 : 내리막 길

[백준 1520] 내리막 길 : https://www.acmicpc.net/problem/1520

1520번: 내리막 길

---

문제 조건 정리

 

1.  한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.
2. 출발 : 최상단 좌측
3. 도착 : 최하단 우측 
4. 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다.

---

입력

 

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

---

문제를 풀기 전

 

1. bfs로 간단하게 구현 가능해보임.
2. 하지만 그렇게 쉬울리가 없음.
3. 시간 복잡도를 계산해보니 뭔가 더 필요하다고 생각함.
4. 가중치와 비슷한 개념인 높이가 있으니 이게 조건뿐만 아니라 다른 활용방법이 있을 것으로 예상함.
5. 다익스트라 개념으로는 문제와 매치가 안됨.
6. 우선순위 큐로 문제 해결할 방법을 찾아냄.
7. 최대 힙을 사용 -> 이동 가능한 지점 중, 가장 높은 지점으로 먼저 이동함.
8. 가장 높은 지점을 이동함으로 중복 이동을 최소화할 수 있다고 판단함.
   
   (이동 가능한 지점 중) 가장 높은 지점을 먼저 이동 VS 일반적으로 이동
   목표 지점을 향해서 이동하는 것을 미룰 수 있음 -> 중복 이동 최소화
   이를 dp로 표현해서 문제를 풀이함.

---

코드

 

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

public class Main {

    private static class Pos implements Comparable<Pos> {
        int m, n;

        public Pos(int m, int n) {
            this.m = m;
            this.n = n;
        }

        // 높이를 기준으로 내림차순으로 정렬
        @Override
        public int compareTo(Pos o) {
            return map[o.m][o.n] - map[this.m][this.n];
        }
    }

    static int[] dm = {1, -1, 0, 0};
    static int[] dn = {0, 0, 1, -1};
    static int m, n;
    static int[][] map;

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");

        // 세로 m, 가로 n 입력
        m = Integer.parseInt(stringTokenizer.nextToken());
        n = Integer.parseInt(stringTokenizer.nextToken());

        map = new int[m][n];

        for (int i = 0; i < m; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(stringTokenizer.nextToken());
            }
        }

        // 우선순위 큐 사용 (내림차순, 최대 힙)
        PriorityQueue<Pos> queue = new PriorityQueue<>();
        queue.offer(new Pos(0, 0));

        // 해당 지점까지 이동할 수 있는 경로의 수를 저장
        // visited 배열의 역할도 가짐
        int[][] dp = new int[m][n];
        // 시작 지점으로 가는 방법은 처음 시작할 때, 한 번
        dp[0][0] = 1;

        while (!queue.isEmpty()) {
            Pos current = queue.poll();
            int currentHeight = map[current.m][current.n];

            for (int d = 0; d < 4; d++) {
                int nextM = current.m + dm[d];
                int nextN = current.n + dn[d];

                // 배열 범위 검사
                if (!isSafe(nextM, nextN)) {
                    continue;
                }
                // 다음 지점으로 이동 가능한지 확인 (높이 체크)
                if (currentHeight <= map[nextM][nextN]) {
                    continue;
                }
                // 해당 지점에 처음 왔다면?
                if (dp[nextM][nextN] == 0) {
                    // 큐에 삽입하고 아래 식으로 이동
                    queue.offer(new Pos(nextM, nextN));
                }
                // 해당 지점으로 올 수 있는 경로의 수 = (1) + (2)
                // (1) 이전에 계산된 해당 지점으로 올 수 있는 경로의 수
                // (2) 해당 지점으로 올 수 있는 이전 지점으로 올 수 있는 경로의 수
                dp[nextM][nextN] += dp[current.m][current.n];

            }
        }

        // 결과 출력
        System.out.println(dp[m - 1][n - 1]);
    }


    private static boolean isSafe(int nextM, int nextN) {
        return 0 <= nextM && nextM < m && 0 <= nextN && nextN < n;
    }
}

 

---

문제를 풀고 난 후

 

포스팅을 위해서 조사해보니 bfs 보다는 dfs 로 풀이하는게 대부분이라 bfs 로 풀이하는게 흥미로웠음!