[1520] 내리막 길 - Java[자바]

 

| 문제 링크

 

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

1520번: 내리막 길

 

 

 

 

---

 

 

 

 

| 문제

 

1. M x N 크기의 지도에 숫자가 적혀있으며, (1,1) 좌표에서 (M,N)좌표로  낮은 숫자의 칸으로만 이동하는 경우의 수를 출력하시오(1 ≤ N ≤ 500), (1 ≤ M ≤ 500).

 

 

 

 

---

 

 

 

| 풀이

 

처음에는 bfs로 풀었다가 메모리 초과가 발생해 일반적인 dfs로 풀었다가 시간 초과가 발생한 문제입니다 :)

다이나믹 프로그래밍을 사용해야 한다는 알고리즘 분류를 보고 dfs를 진행했습니다.

 

1. 입력 값을 받을 2차원 배열 map과 경로를 나타낼 2차원 배열 route(default를 -1로 설정)를 생성
2. dfs(row,col)를 진행하면서 row와 col이 n-1, m-1에 도달한 경우 1을 리턴
3. route[row][col]가 -1이 아닌 경우(이미 지나간 경로가 있는 경우) 해당 값 리턴
4. route[row][col]이 0인 경우 사방 탐색하며, 탐색한 좌표의 값이 더 작은 경우 해당 좌표로 dfs 진행

 

이렇게 dfs를 진행할 경우 (M,N) 좌료를 시작으로 (1,1)까지 오는 경로에서 경로가 늘어날 때 마다 숫자가 1씩 늘어나, 몇 번째 경로인지 나타나게 됩니다.

 

 

 

 

 

 

---

 

 

 

 

| 코드

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {
	
	public static int n;
	public static int m;
	public static int[][] map;
	public static int[][] route;
	public static int[][] delta = {{-1,0},{0,1},{1,0},{0,-1}};

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map = new int[n][m];
		route = new int[n][m];
		
		for(int r = 0; r<n; r++) {
			st = new StringTokenizer(br.readLine());
			for(int c = 0; c<m; c++) {
				map[r][c] = Integer.parseInt(st.nextToken());
				route[r][c]=-1;
			}
		}
		System.out.println(dfs(0,0));
		
	}
	
	public static int dfs(int r, int c) {
		if(r==n-1 && c==m-1)
			return 1;
		if(route[r][c] != -1) {
			return route[r][c];
		}else {
			route[r][c] =0;
			for(int i = 0; i<4; i++) {
				int dr = r+delta[i][0];
				int dc = c+delta[i][1];
				if(dr<0 || dr>=n || dc<0 || dc>=m || map[dr][dc]>=map[r][c])
					continue;
				route[r][c]+=dfs(dr,dc);
			}
		}
		
		return route[r][c];
	}

}