[백준] 1520번 내리막 길

   해당 문제의 원문은 여기서 확인하자.

문제 이해

   높이가 쓰여있는 M * N 배열이 있다. (0, 0)에서 출발하여 (M - 1, N - 1) 지점으로 가려고 할 때, 항상 현재 높이보다 낮은 곳으로만 이동해서 갈 수 있는 경우의 수를 구하는 문제이다. 이동은 인접한 곳(상하좌우)만 가능하다.

   첫째 줄에는 M과 N이 주어지고, 다음 M개의 줄에 걸쳐 한 줄에 N개씩 높이가 공백을 사이에 두고 주어진다. 제한 사항은 다음과 같다.

 

• 1 ≤ M, N ≤ 500
• 1 ≤ 높이 ≤ 10,000
• 0 ≤ 결과 ≤ 10억

 

---

접근 방식

   DFS와 DP의 개념을 이용해 문제를 해결하였다. 문제에서 볼 수 있듯이 경우의 수가 많아 DFS만 사용하게 되는 경우 시간 초과가 발생할 수 있다. 때문에 특정 위치에서 가능한 경우를 저장해두는 방식을 추가하였다. 즉, 한 번 방문했던 위치를 다음에 다시 방문하게 되는 경우, 이미 탐색을 통해 확인했던 유효한 경로의 수를 반환함으로써 중복 탐색을 방지하는 것이다. 다음 예제를 통해 자세히 알아보자.

 

좌측 : 높이, 우측 : 방문 여부 및 유효한 경로 수

 

   -1로 초기화된 이유는 0으로 초기화한 경우 해당 위치에서 유효한 경로의 수가 0인지, 방문이 처음이기에 0인지 구분이 불가능하기 때문이다. 따라서 -1인 경우 처음 방문, 0인 경우 유효한 경로가 없음으로 구분한다.

   과정은 우선 4방향 탐색을 통해 도달 가능한 경로를 찾는다. 방문한 위치는 방문 여부 구분을 위해 -1을 0으로 초기화하며 경로를 찾아나간다.

 

 

   도착지점에 도달한 경우 유효한 경로를 찾았기 때문에 이전 위치에 카운트를 해준다.

 

   

   다른 방향으로도 탐색을 진행하며 과정을 반복한다.

 

 

   이제 다른 방향을 탐색을 진행해보자.

 

 

   현재 도달한 위치를 보면 이전에 찾은 유효한 경로가 1가지 있음을 알 수 있다. 더 이상 탐색을 진행할 필요없이 해당 값을 반환해주면 된다.

 

 

   최종적으로 시작 위치에 유효한 경로의 수가 저장된다.

---

코드

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

public class 백준1520번 {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer token;
    //4방향 탐색 정의
    static final int[] X = {-1, 1, 0, 0};
    static final int[] Y = {0, 0, -1, 1};
    static int M, N;

    public static void main(String[] args) throws IOException {
        token = new StringTokenizer(br.readLine());
        M = Integer.parseInt(token.nextToken());
        N = Integer.parseInt(token.nextToken());
        //0은 높이, 1은 해당 위치를 통해 갈 수 있는 경로 수
        int[][][] map = new int[M][N][2];

        for (int i = 0; i < M; i++) {
            token = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j][0] = Integer.parseInt(token.nextToken());
                //-1인 경우 처음 방문하는 곳
                map[i][j][1] = -1;
            }
        }

        System.out.println(DFS(map, 0, 0));
    }

    public static int DFS(int[][][] map, int x, int y) {
        //도착하면 유효한 경로이므로 1 반환
        if (x == N - 1 && y == M - 1)
            return 1;

        //처음 방문하는 경우만 탐색 진행
        if (map[y][x][1] == -1) {
            //횟수 카운트를 위해 0으로 초기화
            map[y][x][1] = 0;
            //4방향 탐색 진행
            for (int i = 0; i < 4; i++) {
                int nextX = x + X[i];
                int nextY = y + Y[i];

                //배열 범위 내인지 판단
                if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= M) continue;
                //내리막길이 아닌 경우
                else if (map[y][x][0] <= map[nextY][nextX][0]) continue;
                //유효한 길 카운트
                map[y][x][1] += DFS(map, nextX, nextY);
            }
        }
        //카운트된 경로 수 반환
        return map[y][x][1];
    }
}