[백준] 1520. 내리막 길 자바(Java) 풀이

1. 접근 방법

  M과 N이 최대 500까지이기에 완전탐색을 할 경우 시간초과가 납니다. 그래서 DP를 이용해 이미 방문한 지점의 경우 다시 방문하지 않도록 중복을 제거해야만 합니다.

내리막 길 예제

이차원 배열 dp[][]를 만듭니다. 그리고 dp에 해당 지점에 도달할 수 있는 경우의 수를 누적해서 저장해야 합니다.

예제를 보면 빨간 박스친 지점에서 중복이 발생합니다. 20 지점의 경우 2가지 방법으로, 15 지점의 경우 총 3가지 방법으로 도착할 수 있습니다.

 

단순히 BFS로만 풀게되면 아직 방문하지 않은 지점을 큐에 담을 때 20 지점이 담긴 후 32 > 30 > 25 > 20 의 경우의 수를 갱신하기 전에 먼저 큐를 빠져나가게 됩니다. 20에 도달할 수 있는 모든 경우의 수가 dp에 담은 후에야 20인 지점이 큐를 빠져나와야 합니다.

 

미룬다

 

접근방법의 핵심은 '미룬다' 입니다. 해당 지점에 도달할 수 있는 모든 경우의 수를 dp에 담을 때까지 해당 지점이 큐를 빠져나가는 것을 미뤄야만 합니다.

그래서 우선순위큐를 이용했습니다. 해당 지점의 높이를 내림차순으로 하는 우선순위큐를 만들어줍니다.(compareTo 이용)

 

우선순위 큐를 이용하면 32 > 20 도달 후 32 > 30 > 25 > 20 을 도달한 후에야 20이 빠져나갈 수 있도록 만들 수 있습니다. 왜냐하면 20은 높이가 낮기 때문에 계속해서 우선순위가 밀리기 때문이죠.

 

기본적으로 다음 지점으로 이동할 때, 다음지점의 dp에 현재 지점의 dp값을 계속해서 더하도록 만들었습니다. 즉, 경우의 수를 계속해서 누적한거죠.

 

마지막에 최종 누적된 값인 dp[N-1][M-1]을 출력하면 됩니다.

2. 코드

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

public class Main {
	private static int[][] dp;
	private static int[] l = {-1,1,0,0};
	private static int[] r = {0,0,-1,1};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");
		int N = Integer.parseInt(input[0]);
		int M = Integer.parseInt(input[1]);

		//입력
		int[][] arr = new int[N][M];
		for (int i = 0; i < N; i++) {
			input = br.readLine().split(" ");
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(input[j]);
			}	
		}
		
		//알고리즘
		dp = new int[N][M];
		PriorityQueue<Node> qu = new PriorityQueue<Node>();
		
		//상하좌우 순으로 자신의 높이보다 작을 경우 큐에 넣는다.
		//0,0 에서부터 시작
		qu.add(new Node(0,0,arr[0][0]));
		dp[0][0] = 1;
		
		while (!qu.isEmpty()) {
			Node newNode = qu.poll();
			int cx = newNode.getX();
			int cy = newNode.getY();
			int cval = newNode.getVal();
			
			for (int i = 0; i < 4; i++) {
				int nx = cx + l[i];
				int ny = cy + r[i];
				
				if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
					int nval = arr[nx][ny];
					//자신보다 값이 낮은 곳으로만
					if (cval > nval) {
						
						//아직 큐에 담은 적이 없다면
						if (dp[nx][ny] == 0) {
							qu.add(new Node(nx, ny, nval));
							dp[nx][ny] += dp[cx][cy]; //현재 dp값을 다음 지점으로 전한다.
						} else {
							//큐에 한번이라도 담은 적이 있다면
							//큐에 담지 말고 dp 값에 내가 지금까지 쌓아온 값을 더한다.
							dp[nx][ny] += dp[cx][cy];
						}
					}
				}
			}
		}
		
		System.out.println(dp[N-1][M-1]);
	}
	
}

class Node implements Comparable<Node> {
	private int x;
	private int y;
	private int val;
	
	Node(int x, int y, int val) {
		this.x = x;
		this.y = y;
		this.val = val;
	}

	//내림차순
	public int compareTo(Node node) {
		if (this.val < node.val) {
			return 1;
		} else if (this.val > node.val) {
			return -1;
		} else {
			return 0;
		}
	}
	
	public int getX() {
		return x;
	}

	public int getY() {
		return y;
	}

	public int getVal() {
		return val;
	}
}