백준 1520번 : 내리막 길[Java]

https://www.acmicpc.net/problem/1520

1520번: 내리막 길

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

public class Main {
	static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int n, m;
    static int[][] map;
    static Stack<int[]> s = new Stack<>();

    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());

        map = new int[n][m];


        //지도 입력받기
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        s.add(new int[] {0, 0}); //시작 지점
        System.out.println(dfs());
    }
	
	public static int dfs() {
		int count = 0;
		while(!s.isEmpty()) {
			int[] now = s.pop();
			int now_x = now[0];
			int now_y = now[1];
			if(now_x == n - 1 && now_y == m - 1) {//도착
				count++;
				continue;
			}
			for(int i = 0; i < 4; i++) {
				if(check(now_x + dx[i], now_y + dy[i])) {
					//높이 같은것도 지우기
					if(map[now_x + dx[i]][now_y + dy[i]] >= map[now_x][now_y])continue; //오르막길
					s.add(new int[] {now_x + dx[i],now_y + dy[i]});
				}
			}
					
		}
		return count;
	}
		
	
	public static boolean check(int x, int y) { //범위 확인
		if(x < n && x >= 0 && y < m && y >= 0) return true;
		return false;
	}
	
}

처음에 map에서 높이가 더 높은거만 걸렀더니 무한루프에 빠져버려서 >=로 바꿔주니 주어진 테스트케이스는 돌아갔었다.

근데 메모리 초과가 떴다.

 

도저히 모르겠어서 그냥 검색했는데 dp로 풀어야한다는걸 알게돼서 고치기로 결정했다.

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

public class Solution {
	static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int n, m;
    static int[][] map;
    static int[][] dp;

    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());

        map = new int[n][m];
        dp = new int[n][m];


        //지도 입력받기 && dp초기화
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = -1;
            }
        }

        System.out.println(dfs(0, 0));
    }
	
	public static int dfs(int x, int y) {
		if(x == n - 1 && y == m - 1) return 1;
		if(dp[x][y] == -1) {
			dp[x][y] = 0;
			
			for(int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if (!check(nx, ny)) continue; 
					
				if(map[x][y] > map[nx][ny])
					dp[x][y] += dfs(nx, ny); //개뻘짓함
				
			}
		}
		return dp[x][y];
	}
		
	public static boolean check(int x, int y) { //범위 확인
		if(x < n && x >= 0 && y < m && y >= 0) return true;
		return false;
	}
}

분명 맞는거 같은데 계속 틀려서 보니까 dp[x][y] += dfs(nx, ny);부분에

dp[nx][ny]라고 적어놓는 실수를 했다...