[Java] 백준 1520 내리막 길

1520 내리막 길 문제 링크

문제

#1

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] arr = new int[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());
            }
        }

        Deque<int[]> list = new ArrayDeque<>();
        int[] point = {0, 0}; // 시작 좌표
        list.add(point);
        int answer = 0;

        while (!list.isEmpty()) {
            point = list.pollFirst(); // 현재 좌표
            int now = arr[point[0]][point[1]];
            if(point[0]==N-1 && point[1]==M-1) answer++;
            if(point[0] != 0) { // 위
                if (now > arr[point[0]-1][point[1]]) {
                    int[] smallP = {point[0]-1, point[1]};
                    list.addLast(smallP);
                }
            }
            if (point[1] != 0) { // 왼쪽
                if (now > arr[point[0]][point[1]-1]) {
                    int[] smallP = {point[0], point[1]-1};
                    list.addLast(smallP);
                }
            }
            if (point[0] < N-1) { // 아래
                if (now > arr[point[0]+1][point[1]]) {
                    int[] smallP = {point[0]+1, point[1]};
                    list.addLast(smallP);
                }
            }
            if (point[1] < M-1) { // 오른쪽
                if (now > arr[point[0]][point[1]+1]) {
                    int[] smallP = {point[0], point[1]+1};
                    list.addLast(smallP);
                }
            }
        }

        System.out.println(answer);
    }
}

• dfs로 풀었더니 메모리 초과 남
• 메모리 줄이려고 별 짓 다 했는데 안됨
• DP로 visited 넣으려고 했는데 경로가 꼬이면 이걸로 해결 안 될 것 같음

#2

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

class Main {
    static int answer = 0;
    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());

        int[][] arr = new int[N][M];
        boolean[][] visited = 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());
            }
        }

        dfs(arr, 0, 0);

        System.out.println(answer);
    }

    static void dfs(int[][] arr, int x, int y) {
        if(x==N-1 && y==M-1) {
            answer++;
            return;
        }
        if(x!=0 && arr[x][y] > arr[x-1][y]) {
            dfs(arr, x-1, y);
        }
        if(y!=0 && arr[x][y] > arr[x][y-1]) {
            dfs(arr, x, y-1);
        }
        if(x<N-1 && arr[x][y] > arr[x+1][y]) {
            dfs(arr, x+1, y);
        }
        if(y<M-1 && arr[x][y] > arr[x][y+1]) {
            dfs(arr, x, y+1);
        }
    }
}

• bfs로 풀었더니 시간 초과 남
• DP를 무조건 써야 풀릴 듯 함

#3

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

class Main {
    static int answer = 0;
    static boolean[][] visited;
    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());

        int[][] arr = new int[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());
            }
        }

        visited = new boolean[N][M];
        dfs(arr, 0, 0);

        System.out.println(answer);
    }

    static boolean dfs(int[][] arr, int x, int y) {
        if((x==N-1 && y==M-1) || visited[x][y]) {
            answer++;
            return true;
        }
        visited[x][y] = true;
        if(x!=0 && arr[x][y] > arr[x-1][y]) { //위
            if(!dfs(arr, x-1, y)) visited[x-1][y] = false;
        }
        if(y!=0 && arr[x][y] > arr[x][y-1]) { // 왼쪽
            if(!dfs(arr, x, y-1)) visited[x][y-1] = false;
        }
        if(x<N-1 && arr[x][y] > arr[x+1][y]) { // 아래
            if(!dfs(arr, x+1, y)) visited[x+1][y] = false;
        }
        if(y<M-1 && arr[x][y] > arr[x][y+1]) { // 오른쪽
            if(!dfs(arr, x, y+1)) visited[x][y+1] = false;
        }
        return false;
    }
}

• DP를 활용해서 겹치는 경로는 다시 탐색 안 할 수 있도록 했는데
• 시간 초과 남