알고리즘

백준 No.1520 내리막 길- JAVA

jaewoo 2023. 4. 24. 14:13

문제

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

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

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

 

 

풀이

DFS를 이용해야하는데 여기서 DP배열을 통해 값을 미리 구한 값을 사용하는 방식으로 해결해야하낟.

(0,0)에서 시작해서 (M-1, N-1)까지의 경로를 탐색하면서 각 위치에서 내리막길로만 이동하여 (M-1, N-1)까지 도달할 수 있는 경우의 수를 dp배열에 저장한다. 이떄 dp[x][y]는 x,y에서 (M-1,N-1)까지 내리막길로만 이동하여 도달할 수 있는 경우의 수를 의미한다.

 

static int DFS(int x, int y){
	if(x == M-1 && y == N-1) return 1; //갈 수 있는 경우의 수 
    
    if(dp[x][y] != Integer.MIN_VALUE) return dp[x][y]; //초기화하지 않은 값으면 그 값 리턴
    
      dp[x][y] = 0; //아래에서 + 때문에 초기화
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || ny < 0 || nx >= M || ny >= N) continue;

            if(map[x][y] > map[nx][ny]) dp[x][y] += DFS(nx,ny); //높이가 낮아야 탐색을 한다.

        }
}

실제로 DFS(0,0)을 호출하면 해당 메소드가 dp[0][0]을 리턴한다. d[0][0]은 다음 순서를 거쳐 값이 결정된다.

 

1. 먼저 (0,0) 위치에서 시작하므로 dp[0][0]값을 0으로 초기화한다.

2. (0,0) 위치에서 상하좌우로 이동하면서 map[x][y] > map[nx][ny]인 위치에 대해서만 DFS 메소드를 재귀호출

3. 재귀호출을 통해 (M-1, N-1)위치에 도달하는 경로의 개수를 찾는다.

4. 이렇게 찾은 경로의 개수를 dp[0][0] 값에 더해준다.

5. 모든 이동 가능한 위치에 대해 위 과정을 반복

6. dp[0][0] 값이 결정되면 해당 값을 리턴한다.

위와 같은 과정을 거쳐서 dp[0][0] 값을 찾게 된다. 만약 dp[0][0] 값이 3이라면 이는 (0,0)에서 (M-1,N-1) 위치까지 이동할 수 잇는 경로의 개수가 3이라는 뜻이다.

 

 

코드


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

public class Main {

    static int M,N;
    static int[][] map,dp;
    static int dx[] = {0,1,0,-1};
    static int dy[] = {1,0,-1,0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        map = 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++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < M; i++) {
          Arrays.fill(dp[i],Integer.MIN_VALUE);
        }

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

    static int DFS(int x, int y){

        if(x == M-1 && y == N-1) return 1;

        if(dp[x][y] != Integer.MIN_VALUE) return dp[x][y]; //방문한 곳이니 탐색 전에 존재하는 값을 던져줌

        dp[x][y] = 0; //아래에서 + 때문에 초기화
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || ny < 0 || nx >= M || ny >= N) continue;

            if(map[x][y] > map[nx][ny]) dp[x][y] += DFS(nx,ny); //높이가 낮아야 탐색을 한다.

        }

        return dp[x][y];
    }
}

'알고리즘' 카테고리의 다른 글

백준 No.15903 카드 합체 놀이 - JAVA  (0) 2023.04.26
백준 No.17390 - JAVA  (0) 2023.04.25
백준 No.1967 트리의 지름- JAVA  (0) 2023.04.21
백준 No.2644 촌수계산- JAVA  (0) 2023.04.20
백준 No.14425 문자열 집합- JAVA  (0) 2023.04.20