1520_내리막길 (Java)

문제

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

출력

첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.

예제 입력 1

4 5
50 45 37 32 30
35 50 40 20 25
30 30 25 17 28
27 24 22 15 10

예제 출력 1

3

풀이 방법

• 문제를 처음 봤을 때, DFS인 것은 알았으나, 그대로 쓰면 무조건 시간초과가 날 것 같았다. (최대 맵 크기가 25000이므로...)
• 방문할 때, 그냥 지나가는 것이 아닌, 이동할 수 있는 경로를 따져 지나갈 수 없는 경우는 아예 탐방할 수 없도록 하였다.

1. 방문 처리용 배열 생성하기

• dp 배열을 생성하여, 모두 -1로 채워넣은 다음, -1(갈 곳이 없다)라면 return 하도록 했다.

2. 사방 탐색을 통해 주변을 탐색하고, 갈 수 있는 곳이면 값을 더해주기

• 사방탐색을 실시하여, 범위 내 일때만! 주변에 내리막길 탐색을 하여 보다 작은 값이 있다면 재귀 호출을 통해 해당 경로에서 이동할 수 있는 경우의 수를 구할 수 있도록 하였다. 이 때, dp는 탐색 전 0으로 초기화 해주어야 함

dfs 코드

전체 코드

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 M, N;
	static int[][] map, dp;
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 }; // 상하좌우

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		map = new int[M][N];
		dp = new int[M][N];
		
		for(int i = 0; i < M; i++) {
			Arrays.fill(dp[i], -1); //dp로 방문 배열 체크...
		}
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		} // 맵에다 넣고..

		int cnt = dfs(0, 0);
		
		System.out.println(cnt);


	}

	public static int dfs(int r, int c) {
		if (r == M - 1 && c == N - 1) {// 끝점이면
			return 1;
		}
		
		if(dp[r][c] != -1) { //방문했으면 필요없음
			return dp[r][c];
		}
		
		int h = map[r][c];
		dp[r][c] = 0;
		// 아직 아니라면 탐방
		for (int d = 0; d < 4; d++) {
			int nr = r + dr[d];
			int nc = c + dc[d];

			if (nr >= 0 && nr < M && nc >= 0 && nc < N) { // 범위 내일 때
				if (map[r][c] > map[nr][nc]) { // 주변이 높이가 더 높다면
					dp[r][c] += dfs(nr, nc);
				}
			}
		}
		
		return dp[r][c];
	}

}

결과

비고

재귀까지는 쉬웠으나, 가는 경로의 수를 dp에 저장한다는 것을 생각하기가 힘들었다...