알고리즘

[백준 1520] 내리막 길 - 자바(java)

김RPG 2025. 4. 14. 14:57
반응형

 

그래프 탐색을 하는데 지금 현재 있는 숫자보다 낮은 곳으로만 가도록 값을 넣어주면 된다!

제일 간단한 방법은 DFS나 BFS를 이용해 끝에 도착했을 때 값을 하나씩 늘리면은 답은 구할 수 있다.

하지만 대부분 BFS로 완전 탐색 하는 경우는 8*8 정도에서는 가능하지만
이게 500* 500으로 갈 경우 시간초과가 날 수 밖에 없다.

 

하지만, 최악의 경우 4^(500 x 500) 가 나오는 이거는 엄청나게 시간이 많이 걸리기 때문에 시간을 줄이는 것이 가장 중요한 과제 인데 

이렇게 라인이 겹치는 것을 볼 수 있다. 

 

그렇다면 DP로 간 길을 확인해 최종 목적지에 도착하면 1을 반환해 최종 목적지로 가는 길이라고 표시하고

이제 다른 길을 탐색하다가 최종 목적지로 가는 길과 만나면 그 길을 통해 최종 목적지로 갈 수 있으니 지금까지 내가 온 길 + 최종 목적지로 갈 수 있는 길을 해서 점화식을 짤 수 있을 것 같다. 

 

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

public class Main {
    static int[] dx = {0, 0,-1, 1};
    static int[] dy = {1,-1, 0, 0};
    static int[][] arr, dp;
    static boolean[][] visit;
    static int N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N][M];
        dp = new int[N][M];
        visit = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        System.out.println(dfs(0, 0));
    }

    public static int dfs(int x, int y) {
        if (x == N - 1 && y == M - 1) {
            return 1;
        }
        if (visit[x][y]) {
            return dp[x][y];
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= N || ny >= M || nx < 0 || ny < 0) continue;
            if(arr[nx][ny] >= arr[x][y]) continue;
            dp[x][y] += dfs(nx, ny);
            visit[nx][ny] = true;

        }

        return dp[x][y];
    }
}

 

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

최종 목적지라면 1을 반환

        if (visit[x][y]) {
            return dp[x][y];
        }

만약 지나갔었던 길이라면 최종 목적지로 가는 길이 몇개인지 반환

 

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= N || ny >= M || nx < 0 || ny < 0) continue;
            if(arr[nx][ny] >= arr[x][y]) continue;
            dp[x][y] += dfs(nx, ny);
            visit[nx][ny] = true;
        }

만약 지도를 벗어나는 거면 continue

다음에 있는 공간이 지금보다 작거나 같을 경우 continue

아니라면 dfs로 탐색하여 최종 목적지로 가는 길까치 찾은 다음 지금 있는 dp[x][y] 와 더하여 값 유지하기 

 

 

cf)

arr[nx][ny] != 0로 길을 탐색했는지 안했는지 하면 안되나요??

저도 맨 처음에 이러면 되겠다 해서 이런식으로 탐색한 길인지 아닌지 판단하였는데요 시간초과가 뜨더라구요 ㅠㅠㅠ

 

arr[nx][ny] 가 0이라면 두가지의 의미를 함축하고 있어서 안됩니다.

1. 아직 탐색하지 않은 길 -> 이경우 visit[nx][ny] 와 같은 뜻입니다.

2. 탐색하였지만 이길로 갔을 때 최종목적지가 나오지 않는 길 -> 이경우 이미 탐색을 하여서 굳이 추가로 탐색할 이유가 없지만, 계속 탐색을 하도록 만드니 시간초과가 뜨더라구요!

 

백준 풀 때 직관적으로 풀기보다 로직을 좀 더 세세히 짜야 한다는 것을 배운 문제였습니다.

반응형