[BJ]1520 내리막길

BJ_G4_1520_내리막길

 

 

문제링크

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

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

BJ G4 1520 내리막길 HD 1080p - YouTube

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l4;

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

/**
 * @author 은서파
 * @since 2021. 9. 23.
 * @see https://www.acmicpc.net/problem/1520
 * @perf 38916	348
 * @category #DP, #DFS
 * @고려사항
 *  overlapping subproblem이면서 optimize substructure이기 때문에 DP를 이용해서 풀어줘야 한다.
 *  memo[i][j] = i, j에서 목적지인 (R-1, C-1)에 도착하는 경우의 수
 *  이때 memo를 이용한 방문 체크 시 초기값을 -1로 잡아주고 방문하면 0으로 일단 초기화 후 탐색 회수를 업데이트 해준다.
 */

public class BJ_G4_1520_내리막길 {

	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer tokens;
	static int R, C;
	static int [][] map;
	// memo[r][c] = map[r][c]에서 map[R-1][C-1]에 도달하는 경우의 수 
	static int [][] memo;
	
	static int [][] deltas = {{-1, 0},{1, 0},{0, -1},{0, 1}};

	public static void main(String[] args) throws IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		R = Integer.parseInt(tokens.nextToken());
		C = Integer.parseInt(tokens.nextToken());
		
		map = new int [R][C];
		for(int r=0; r<R; r++) {
			tokens = new StringTokenizer(input.readLine());
			for(int c=0; c<C; c++) {
				map[r][c] = Integer.parseInt(tokens.nextToken());
			}
		}// 입력 완료!!
		
		memo = new int [R][C];
		// 배열의 초기값은 0 --> 길이 없는건지(0), 아니면 안가본건지 알수가 없다.
		for(int [] row: memo) {
			Arrays.fill(row, -1);
		}
		// 일종의 기저조건
		memo[R-1][C-1]=1;
		
		// 0, 0에서 사방탐색으로 출발해서 답을 찾아보자.
		int answer = find(0, 0);
		System.out.println(answer);
	}
	
	private static int find(int r, int c) {
		//memo 활용
		if(memo[r][c]!=-1) {
			return memo[r][c];
		}
		// -1이라면 처음 방문한 경우 - 현재 지점을 0으로 초기화 하고 자식 탐색 --> memo에 결과 업데이트
		memo[r][c]=0;
		for(int d=0; d<deltas.length; d++) {
			int nr = r + deltas[d][0];
			int nc = c + deltas[d][1];
			// 범위 안에 있고.. 내리막길이라면 가보자!! , 일반적인 4방 탐색에서는 visited 배열을 이용해서 왔던길 안가도록 처리 필요
			// 여기서는 무조건 내리막으로만 이동 --> 따라서 왔던 길을 다시 가는 불상사는 발생할 리가 없다.
			if(isIn(nr, nc) && map[r][c]>map[nr][nc]) {
				memo[r][c]+=find(nr, nc);
			}
		}
		return memo[r][c];
	}
	
	
	private static boolean isIn(int r, int c) {
		return 0<=r && r<R && 0<=c && c<C;
	}

	// REMOVE_START
	private static String src = "4 5\r\n" +
			"50 45 37 32 30\r\n" +
			"35 50 40 20 25\r\n" +
			"30 30 25 17 28\r\n" +
			"27 24 22 15 10";
	// REMOVE_END

}