[백준/JAVA] 1520번 내리막 길

 

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

1520번: 내리막 길

문제분석

현재 자신이 있는 위치보다 낮은 위치로 갈 수 있고 0,0 에서 n-1,m-1까지 갈 수 있는 경로의 개수를 구하는 문제이다.

 

코드

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int r,c,answer;
	static int[][] arr;
	static int[][] enable;
	static int[] dx = {0,1,0,-1};
	static int[] dy = {1,0,-1,0};

	static void init(){
		answer = 0;
		arr = new int[r][c];
		enable = new int[r][c];
		for(int i=0; i<r; ++i) Arrays.fill(enable[i],-1);
		enable[r-1][c-1] = 1;
		enable[0][0] = 0;
	}

	static boolean dfs(int x, int y){
		boolean flag = false;
		for(int i=0; i<4; ++i){
			int nx = x+dx[i];
			int ny = y+dy[i];
			if(nx<0 || ny<0 || nx>=r || ny>=c) continue;
			if(arr[nx][ny]>=arr[x][y] ) continue;
			if(enable[nx][ny]!=-1){
				enable[x][y] += enable[nx][ny];
				flag = true;
				continue;
			}
			enable[nx][ny] = 0;
			if(dfs(nx,ny)){
				enable[x][y] += enable[nx][ny];
				flag = true;
			}
		}
		return flag;
	}

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		init();
		for(int i=0; i<r; ++i)
			arr[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		dfs(0,0);
		System.out.println(enable[0][0]);

	}
}

 

문제 풀이

처음엔 dfs로 모든 가능한 경우의수를 탐색함. ==> 시간초과

enable배열을 모두 -1로 초기화 시킨 후 

1. 각 칸이 -1이면 아직 방문하지 않은 지점

2. -1이 아니라면 방문을 한 지점, 값은 그 칸에서 (n-1, m-1)에 도달할 수 있는 방법의 가짓 수

enable[i][j] 가 -1이라면 방문하지 않은 칸이므로 dfs진행, 

enable[i][j] 가 -1이 아니라면 현재까지 지나온 길에 enable[i][j] 의 값을 더해줌

최종적으로 enable[0][0]은 0,0부터 n-1,m-1까지 도달할 수 있는 방법의 가짓 수