백준 1520 내리막 길 (Gold 3, SW)

전략

• 1번 전략(처음 시도했던 방식)

  • 2차원 배열 순회하면서 자기로 들어오는 노드를 DP배열에 저장 (높이가 높은 곳에서 흘러 들어오는)
    
    
  • 0인 노드가 있다면 그 노드로 부터 이동하는 모든 경로는 의미가 없다 -> 그 노드 부터 DFS로 돌면서 0인 노드가 있다면 propagation시킨다.
    
    
  • 다시 2차원 순회하면서 자신에게 들어오는 Node들을 DP로 계산
    
    
  • 가장 큰 문제 1: 여긴 방향성이 존재하지 않는다 즉 항상 최적의 경로로 이동하는 것이 아니기 때문에 어떤 방향으로 DP를 업데이트 할 것인지 알 수 없음
    
    
  • 가장 큰 문제 2: 1번의 이유로 배열 순회를 시작 노드부터 끝 노드까지 탐색할 수가 없다 즉 (0,1)이 반드시 (0,0)다음으로 탐색된다는 보장이 없다. -> 다른 노드를 돌고 나중에 (0,1)에 도달할 수도 있다
    
    

• 전략 2 (아이디어를 받아서 푼 것)

  • 갈 수있는 경로를 그려보니 시작 노드부터 그냥 평범하게 DFS를 탐색해서 종료 노드까지 가는 케이스들이 나옴
    
    
  • 여기서 경로가 겹치는 부분이 나오는 곳 부터 DP를 이용할 수 있다.
    
    
  • 즉 (0,0) -> (3,4) == (0,0) -> (3,3) -> (3,4) 이고 (3,3) -> (3,4) 케이스는 3가지 모든 경우의 수의 중복 경로 이므로 DP로 저장할 수 있다.
    
    
  • 점화식으로 세워보면 DP[i][j] 가 if 방문한 적 없는 루트라면 0으로 초기화 & 만약 도착지에 도달 -> 백트래킹으로 경로수 += 1 else 방문한 적이 있다면 이전 DP[i-1][j], DP[i][j-1] .... += DP[i][j] 방식으로 업데이트 한다

정답코드

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

public class DeclineRoad {

	//M x N array
	static int M;
	static int N;
	static int [][] Route;
	static int [][] Income;
	static boolean [][] visited;
 	static int [][] DP;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String [] in = br.readLine().split(" ");
		M = Integer.parseInt(in[0]);
		N = Integer.parseInt(in[1]);
		
		Route = new int[M][N];
		DP = new int[M][N];
		visited = new boolean[M][N];
		
		for(int i = 0; i < M; i++) {
			Arrays.fill(DP[i], -1);
		}
		
		for(int i = 0; i < M; i++) {
			String[] input = br.readLine().split(" ");
			for(int j = 0; j < N; j++) {
				Route[i][j] = Integer.parseInt(input[j]);
			}
		}
		
		System.out.println(DFS(0,0));
	}
	
	public static int DFS(int x, int y) {
		
		//도착지에 도달했다면 경로 1개를 리턴 
		if(x==(M-1) && y==(N-1))return 1;
		
		//Memorization 
		if(DP[x][y] != -1) return DP[x][y];
		
		//visited 대신 쓴다
		DP[x][y] = 0;
		
		int pivot = Route[x][y];
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx<0||nx>=M||ny<0||ny>=N||pivot<=Route[nx][ny])continue;
			
			DP[x][y] += DFS(nx,ny);
			
		}
		
		return DP[x][y];
		
	}
	
}