[골드3] 1520. 내리막길

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

1520번: 내리막 길

엥 이모티콘 입력이..??

---

※  문제를 요약하면 아래와 같습니다.

▶ 누가 지도를 구했는데 직사각형 모양이며 여러 칸으로 구성

▶ 한 칸은 한 지점의 높이를 나타내는데, 각 지점사이의 이동은 지도에서 상하좌우 이웃된 곳만 가능

▶ 제일 왼쪽 위 칸에서 제일 오른쪽 아래 칸 지점으로 이동하는 것이 목표

▶ 이동은 항상 높이가 낮은 곳으로만 이동이 가능할 때, 가능한 경로 개수 구하기

 ex) 아래 예시 맵에서는 3가지 경우로만 가능하다

▶  Input : 첫번째 줄에 지도의 세로의 크기 M과 가로의 크기 N이 공백 구분으로 입력, 이어 MxN사이즈 맵의 값이 입력

                 ( M <=500, N <= 10000 )

▶  Output : 첫째줄에 이동 가능한 경로의 수 출력

---

◈ Input - 1

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

◈ Output - 1

3

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 이차원 배열로 맵의 값을 저장

▶ 델타 탐색 방법으로 왼쪽 위 원소부터 DFS 탐색

▶ 방문처리를 boolean형 배열로 저장하여 모든 구간 탐색 하여 이동 시 시간초과 발생 (ㅂㄷㅂㄷ,,)

▶ 방문처리를 int형 배열로 저장하여 방문하지 않은 곳은 -1로 지정, 방문한 곳은 0으로 변경

▶ 어떠한 경로가 오른쪽 맨아래 도착 시 해당 경로의 방문처리 배열 모두 +1 카운트 ( 동적 계획법! )

▶ 경로 탐색 도중 방문처리 배열값이 -1이 아닐 경우 해당 좌표의 방문처리 배열값 return

▶ 이미 지나간 경로를 만났을 경우 해당 경로 탐색 종료 ( 탐색하지 않아도 해당 경로는 오른쪽 아래로 이어진다.)

▶ 탐색이 종료되어 값이 반환되는 과정에서 상,하,좌,우 방문처리 배열의 값들의 합을 방문처리 값으로 입력

 ex ) 위 문제의 예시에서의 방문배열 변화

최초의 방문 배열

왼쪽에서 오른쪽 아래로 가는 첫경로 탐색~반환 과정

최종 3경로 전부 탐색 후 방문 배열 결과

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
	static int[][] narrMap;
	static int[][] narrDP;
	static int nCount;
	static int M, N;

	// 동서남북
	static int[] dr = { 0, 0, 1 , -1};
	static int[] dc = { 1, -1, 0, 0 };

	public static void main(String[] args) throws IOException {
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(bReader.readLine());
		
        	// Row, Col 입력 받아주고
		M = Integer.parseInt(st.nextToken()); // Rows
		N = Integer.parseInt(st.nextToken()); // Cols

		// 방문 배열 선언해주고
		narrDP = new int[M][N];
		
		for(int i = 0; i < M; i++) {
			for(int j = 0; j < N; j++) 
				narrDP[i][j] = -1;
		}
		narrMap = new int[M][N];
		// 지도 값 입력 받고
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(bReader.readLine());
			for(int j = 0 ; j < N; j++) {
				narrMap[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		// DFS 탐색 시작
		nCount = DFS(0,0);
		
		bWriter.write(String.valueOf(nCount));
		
		bWriter.flush();
		bWriter.close();
	}

	public static int DFS(int nRow, int nCol) {
		// 기저 조건
		if(nRow == M-1 && nCol == N-1) {
			return 1;
		}
		
		if (narrDP[nRow][nCol] > -1)
			return narrDP[nRow][nCol];
		
		// 탐색 조건
		// 본인보다 작은 값만 찾아간다아
		narrDP[nRow][nCol] = 0;
		for (int k = 0; k < dr.length; k++) {
			int nRowSearch = nRow + dr[k];
			int nColSearch = nCol + dc[k];

			// 동, 서, 남, 북 중 높이가 낮은 곳만!
			if (nRowSearch >= 0 && nColSearch >= 0 && nRowSearch < M && nColSearch < N
					&& narrMap[nRow][nCol] > narrMap[nRowSearch][nColSearch]) {
                    	// 방문 배열 값에 넣어주기
				narrDP[nRow][nCol] += DFS(nRowSearch, nColSearch);
			}
		}
		// 방문 배열 값 return
		return narrDP[nRow][nCol];
	}
}

DFS 공부하다 웬 동적 계획법,,,

Good Luck! (피드백 감사합니다!)