백준 1520 java - 내리막길(DP, 동적계획법)

문제, 입출력, 테스트케이스

해당 문제는 자력으로 푼 건 아니고 다른 분의 풀이를 참고하여 푼 것이다. 왜 Queue를 사용한 bfs는 안되는 걸까 생각하다가 힙을 쓰면 된다고 생각하니 풀렸다. 정석으로는 탑다운 방식의 DP였다.

 

 

<문제 풀이/접근과정>
1. 내리막길의 개념은 현재 방문한 곳의 높이(값) 보다 다음에 방문할 곳의 값이 더 낮은 경우이다.
2. BFS+DP또는 DFS+DP로 풀면 된다.
3. 두 가지 접근법이 있는데 0,0(시작점-바텀업) 부터 아래로 쌓거나, M-1, N-1(도착점-탑다운)부터 쌓으면 된다.
4. 해당 문제는 dp다 보니까 탑다운, 바텀업 전부 되지만 나는 바텀업(0,0 부터 쌓기)방식으로 풀었다.
5. PriorityQueue를 쓰지 않으면 주변 내리막길이란 내리막길은 다 가기 때문에내리막길 다음의 그다음 제일 큰 내리막길로 가게끔 해서 자동으로 경로의 수를 쌓게 하는 방식이다.

 

<소스 코드>

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Boj_1520 {
	static int M, N, arr[][], delta[][] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } }, dp[][];

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

		stz = new StringTokenizer(br.readLine());

		M = Integer.parseInt(stz.nextToken());
		N = Integer.parseInt(stz.nextToken());
		arr = new int[M][N];
		dp = new int[M][N];

		for (int i = 0; i < M; i++) {
			stz = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				arr[i][j] = Integer.parseInt(stz.nextToken());
			}
		}

		bfs(0, 0);
		System.out.println(dp[M - 1][N - 1]);
	}

	private static void bfs(int startR, int startC) {
		PriorityQueue<int[]> q = new PriorityQueue<>(new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return arr[o2[0]][o2[1]] - arr[o1[0]][o1[1]];
			}
		});
		
		dp[0][0] = 1;
		q.add(new int[] { startR, startC });
		
		while (!q.isEmpty()) {
			int size = q.size();

			for (int i = 0; i < size; i++) {
				int temp[] = q.poll();
				int r = temp[0];
				int c = temp[1];
				if (r == M - 1 && c == N - 1)
					continue;
				for (int j = 0; j < delta.length; j++) {
					int nr = r + delta[j][0];
					int nc = c + delta[j][1];

					if (!check(nr, nc))	continue;
					if (arr[r][c] > arr[nr][nc]) {

						if(dp[nr][nc] == 0)	q.add(new int[] { nr, nc });
						dp[nr][nc] += dp[r][c];
					}
				}

			}
		}

	}

	private static boolean check(int nr, int nc) {
		return 0 <= nr && nr < M && 0 <= nc && nc < N;
	}
}