BOJ - 1520 ) 내리막길

 

---

 

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

1520번: 내리막 길

---

3가지를 체크해주자.

 

1. 첫번째가는 길이여서 N,M까지 갈수있는 길인지?

2. 두번이상 째에 가는 길인데 N,M까지 갈수있는 경로인지 ( visit[0][y][x] 값이 양수)

3. 두번째 이상가는길인데 N,M까지 갈수 없어서 갈 필요가 없는 길인지?

 

3번째고려요소를 놓쳐 예전에 못풀었던 문제였다. 즉 첫번째 탐색했을때 N,M까지 못가면,

이후 탐색에서 그쪽길로 가면안된다는 체크를 해주어야한다.

---

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

public class 내리막길 {
	public static int n, m , map[][] , visit[][][] , dir[][] = {{1,0},{-1,0},{0,1},{0,-1}};
	public static void main(String[] args) throws Exception {
		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];
		visit = new int[2][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());
				
			}
		}
		int answer = Dfs(0,0);
		System.out.println(answer);
	}
	private static int Dfs(int y, int x) {
		if(y==n-1 && x == m-1) {
			return 1;
		}
		if(visit[1][y][x] < 0) return 0;
		else if(visit[1][y][x] ==0) {
			visit[1][y][x] =1;
			for(int i = 0 ; i < 4 ; i ++) {
				int ny = y+dir[i][0] , nx = x +dir[i][1];
				if(ny>=0&&nx>=0&&ny<n&&nx<m&&map[y][x]>map[ny][nx]) {
					visit[0][y][x] += Dfs(ny,nx);
				}
			}
			return visit[0][y][x];
		} else {
			return visit[0][y][x];
		}
	}
}

---