BOJ 1520 내리막길 Java

BOJ 1520 내리막길 Java

 

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

1520번: 내리막 길

 

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

public class Main {
	public static void main(String[] args) throws Exception {
		new Main().solve();
	} // main
	
	int M, N;
	int[][] map, answer;
	boolean[][] visited;
	void input() throws Exception {
		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];
		answer = new int[M][N];
		visited = new boolean[M][N];
		isEnd = new boolean[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());
			}
		}
	}
	
	void solve() throws Exception {
		input();
		visited[0][0] = true;
		dfs(0, 0);
		
		System.out.println(answer[0][0]);
	} // solve
	
	int[][] dir = new int[][] { {-1,0},{0,1},{1,0},{0,-1} };
	boolean[][] isEnd;
	int dfs(int x, int y) {
		if(isEnd[x][y] || answer[x][y] > 0) {
			return answer[x][y];
		}
		if(x == M-1 && y == N-1) {
			return 1;
		}
		
		for (int d = 0; d < 4; d++) {
			int nx = x + dir[d][0];
			int ny = y + dir[d][1];
		
			if(!isInBound(nx, ny) || visited[nx][ny] || map[nx][ny] >= map[x][y]) continue;
			visited[nx][ny] = true;
			answer[x][y] += dfs(nx, ny);
			visited[nx][ny] = false;
		}
		isEnd[x][y] = true;
		return answer[x][y];
	} // dfs
	
	boolean isInBound(int x, int y) {
		if(x < 0 || y < 0 || x >= M || y >= N) return false;
		return true;
	}
}

 

500x500 배열이라 시간 넉넉할 줄 알았는데 시간초과 나길래 DP 문제구나 했다.. 하하

앞으로는 문제조건 체크 필수..

 

dfs + dp 문제로 각 칸에 이미 경로계산이 끝난 애들은 표시해서 바로 반환해주어야 한다.

 

그래서 solve 함수 내에서

if(isEnd[x][y] || answer[x][y] > 0) {
	return answer[x][y];
}

이렇게 바로 return 한다.

 

isEnd 배열은

답이 0인 경우가

 1) 이미 계산 다 해봤더니 경로 개수가 0인 경우

 2) 아직 계산이 안 되어서 초기값 0 인 경우

 

두 가지로 나뉘기 때문에

이미 계산한 후인 0을 체크해야해서

isEnd 라는 boolean 배열에서 true이면 바로 0을 리턴했다.

 

solve 함수 내 방향 4가지 돌면서 answer 배열에 dfs 리턴 결과를 더한다.

기본 골격은 dfs와 같다.