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

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

1520번: 내리막 길

 

 

| 문제 해결방법

 

2차원 배열에서 목표지점까지 갈 수 있는 경로의 개수를 구하는 문제이다.

 

관련 알고리즘 : DFS + DP

 

 

핵심 아이디어는

 

방문했던 길을 한번 더 방문하지 않는 것

 

방문하지 않은 길을 한번 탐색하면,

결과는 두 가지가 나올 수 있다.

 

1. goal까지 갈 수 있는 경우

2. 사방으로 더이상 갈 길이 없는 경우

 

 

알고리즘 순서

 

1. 처음에 2차원 dp배열을 만든 후 -1로 초기화 해준다

 

2. find(int r, int c)메서드에서 재귀 탐색을 한다. ( find함수는 0,0 에서 시작 )

 

      (기저조건 :  goal까지 도착했다면 1을 return 한다.)

 

      현재 위치에 0의 값을 넣어준다.(방문 했다는 의미)

 

3. 그리고 for문으로 사방탐색을 하면서

 

      배열 범위를 벗어나지 않는지, 다음 지점이 내리막길인지

 

4. 검사한 후 위 조건에 해당하면

 

      사방탐색한 dp값이 

 

          -1일 경우 =  아직 탐색하지 않은 길

 

          1보다 크거나 같은 경우 =  goal까지 갈 수 있는 길의 경로의 개수

 

          0일 경우 =   goal까지 갈 수 없는 길

 

      이 된다.

 

[JAVA] 해설 코드

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

public class Main {
	static int N, M;
	static long[][] arr;
	static long[][] dp;
	static int[][] dir= {{0,1},{1,0},{0,-1},{-1,0}};
	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());
		arr = new long[N][M];
		dp = new long[N][M];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<M;j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());	
			}
		}

		for(long[] a : dp) {
			Arrays.fill(a, -1);
		}
		
		System.out.println(find(0,0));
		
	
	}
	private static long find(int r, int c) {
		
		if(r == N-1 && c == M-1) {
			return 1;
		}
		
		dp[r][c] = 0;
		
		for(int i=0;i<4;i++) {
			int nextR = r + dir[i][0];
			int nextC = c + dir[i][1];
			
			if(isIn(nextR,nextC) && arr[r][c] > arr[nextR][nextC]) {
				
				// 처음 방문하는 곳이라면
				if(dp[nextR][nextC] == -1)
					dp[r][c] += find(nextR,nextC);
				// 방문했던 곳이라면 
				else if(dp[nextR][nextC] >= 1)
					dp[r][c] += dp[nextR][nextC];
				// dp[nextR][nextC] == 0 어떤 동작도 하지 않고 pass
			}			
		}
		
		return dp[r][c];
	}
	
	private static boolean isIn(int r, int c) {
		return r<N && r>=0 && c<M && c >=0;
	}
}

 

[제출] 메모리 및 시간