백준_내리막길_1520

문제 링크

조건

• 지도의 크기 : M x N (1 <= M,N <= 500)
• 지도 각 지점의 높이는 10000 이하의 자연수

 

접근 방법

• dfs 완탐 시 시간초과
• memoization 활용
  
  • memo[][] 배열 선언 : 모든 요소 -1 초기화
  • (0, 0)에서 dfs 탐색 출발하여 탐색하는 길목에 경우의 수 memoization 진행
  • 만약 memo[i][j] == -1 이면 최초 방문이므로 0으로 방문 처리하고 dfs 탐색 계속 진행
  • 만약 memo[i][j] >= 0 이면 이전 탐색에서 이미 경우의 수가 memo[i][j] 개 임을 구한 것이므로 곧바로 return
  • 깊이가 너무 깊은 dfs 시에는, memoization으로 이전 탐색 결과를 기록해놓음으로써 같은 탐색을 반복하는 리소스를 줄일 수 있음 

 

솔루션

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 R, C; // M*N
	static int[][] height; // 높이 저장
	static int[][] memo;
	static int[] dr = {-1,1,0,0};
	static int[] dc = {0,0,-1,1};
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
		
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
	
		height = new int[R][C];
		memo = new int[R][C];
		
		for(int i = 0; i < R; i++) {
			Arrays.fill(memo[i], -1); // 미방문 처리
		}
		
		for(int i = 0; i < R; i++) { // map 입력
			st = new StringTokenizer(br.readLine().trim(), " ");
			for(int j = 0; j < C; j++) {
				height[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		dfs(0,0);
		
		System.out.println(memo[0][0]);
		
	}
	private static int dfs(int r, int c) {
		if(r == R-1 && c == C-1) {
			return 1;
		}
		
		if(memo[r][c] >= 0) { // 이미 이전에 탐색했던 길
			return memo[r][c];
		}
		if(memo[r][c] == -1) { // 최초로 방문한 경우 방문체크
			memo[r][c] = 0;
		}
		
		int nr,nc;
		for(int i = 0; i < 4; i++) {
			nr = r + dr[i];
			nc = c + dc[i];
			if(nr < 0 || nr >= R || nc < 0 || nc >= C || height[r][c] <= height[nr][nc]) continue;
			if(memo[nr][nc] == 0) continue; // 방문했던 길인데 [R-1][C-1] 까지 도달할 수 있는 경우의 수가 0이라면 가볼 필요 X => 가지치기
			
			memo[r][c] += dfs(nr,nc);
		}
		
		return memo[r][c];
		
	}
}

 

리뷰

• dfs는 깊이 우선 탐색이라 N이 클 경우 무조건 시간초과가 남! => dfs와 가지치기, 메모이제이션은 항상 묶어서 생각할 것