[Algorithm] ๐Ÿ›ฃ๏ธ๋ฐฑ์ค€ 1520 ๋‚ด๋ฆฌ๋ง‰ ๊ธธ

0. ๋ฌธ์ œ

์—ฌํ–‰์„ ๋– ๋‚œ ์„ธ์ค€์ด๋Š” ์ง€๋„๋ฅผ ํ•˜๋‚˜ ๊ตฌํ•˜์˜€๋‹ค. ์ด ์ง€๋„๋Š” ์•„๋ž˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์ด ์ง์‚ฌ๊ฐํ˜• ๋ชจ์–‘์ด๋ฉฐ ์—ฌ๋Ÿฌ ์นธ์œผ๋กœ ๋‚˜๋‰˜์–ด์ ธ ์žˆ๋‹ค. ํ•œ ์นธ์€ ํ•œ ์ง€์ ์„ ๋‚˜ํƒ€๋‚ด๋Š”๋ฐ ๊ฐ ์นธ์—๋Š” ๊ทธ ์ง€์ ์˜ ๋†’์ด๊ฐ€ ์“ฐ์—ฌ ์žˆ์œผ๋ฉฐ, ๊ฐ ์ง€์  ์‚ฌ์ด์˜ ์ด๋™์€ ์ง€๋„์—์„œ ์ƒํ•˜์ขŒ์šฐ ์ด์›ƒํ•œ ๊ณณ๋ผ๋ฆฌ๋งŒ ๊ฐ€๋Šฅํ•˜๋‹ค.

ํ˜„์žฌ ์ œ์ผ ์™ผ์ชฝ ์œ„ ์นธ์ด ๋‚˜ํƒ€๋‚ด๋Š” ์ง€์ ์— ์žˆ๋Š” ์„ธ์ค€์ด๋Š” ์ œ์ผ ์˜ค๋ฅธ์ชฝ ์•„๋ž˜ ์นธ์ด ๋‚˜ํƒ€๋‚ด๋Š” ์ง€์ ์œผ๋กœ ๊ฐ€๋ ค๊ณ  ํ•œ๋‹ค. ๊ทธ๋Ÿฐ๋ฐ ๊ฐ€๋Šฅํ•œ ํž˜์„ ์ ๊ฒŒ ๋“ค์ด๊ณ  ์‹ถ์–ด ํ•ญ์ƒ ๋†’์ด๊ฐ€ ๋” ๋‚ฎ์€ ์ง€์ ์œผ๋กœ๋งŒ ์ด๋™ํ•˜์—ฌ ๋ชฉํ‘œ ์ง€์ ๊นŒ์ง€ ๊ฐ€๊ณ ์ž ํ•œ๋‹ค. ์œ„์™€ ๊ฐ™์€ ์ง€๋„์—์„œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์„ธ ๊ฐ€์ง€ ๊ฒฝ๋กœ๊ฐ€ ๊ฐ€๋Šฅํ•˜๋‹ค.

์ง€๋„๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ ์ด์™€ ๊ฐ™์ด ์ œ์ผ ์™ผ์ชฝ ์œ„ ์ง€์ ์—์„œ ์ถœ๋ฐœํ•˜์—ฌ ์ œ์ผ ์˜ค๋ฅธ์ชฝ ์•„๋ž˜ ์ง€์ ๊นŒ์ง€ ํ•ญ์ƒ ๋‚ด๋ฆฌ๋ง‰๊ธธ๋กœ๋งŒ ์ด๋™ํ•˜๋Š” ๊ฒฝ๋กœ์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…๋ ฅ
์ฒซ์งธ ์ค„์—๋Š” ์ง€๋„์˜ ์„ธ๋กœ์˜ ํฌ๊ธฐ M๊ณผ ๊ฐ€๋กœ์˜ ํฌ๊ธฐ N์ด ๋นˆ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฃผ์–ด์ง„๋‹ค. ์ด์–ด ๋‹ค์Œ M๊ฐœ ์ค„์— ๊ฑธ์ณ ํ•œ ์ค„์— N๊ฐœ์”ฉ ์œ„์—์„œ๋ถ€ํ„ฐ ์ฐจ๋ก€๋กœ ๊ฐ ์ง€์ ์˜ ๋†’์ด๊ฐ€ ๋นˆ ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฃผ์–ด์ง„๋‹ค. M๊ณผ N์€ ๊ฐ๊ฐ 500์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๊ณ , ๊ฐ ์ง€์ ์˜ ๋†’์ด๋Š” 10000์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋‹ค.

์ถœ๋ ฅ
์ฒซ์งธ ์ค„์— ์ด๋™ ๊ฐ€๋Šฅํ•œ ๊ฒฝ๋กœ์˜ ์ˆ˜ H๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ๋ชจ๋“  ์ž…๋ ฅ์— ๋Œ€ํ•˜์—ฌ H๋Š” 10์–ต ์ดํ•˜์˜ ์Œ์ด ์•„๋‹Œ ์ •์ˆ˜์ด๋‹ค.

1. ์•„์ด๋””์–ด

BFS๋ฅผ ์žฌ๊ท€๋กœ ๋ฐ”๊พผ ํ›„, ํ˜„์žฌ ๋†’์ด๋ณด๋‹ค ์ž‘์œผ๋ฉด ์ด๋™ ๊ฐ€๋Šฅํ•จ!

2. ํ•ต์‹ฌ ํ’€์ด

BFS๋ฅผ ์žฌ๊ท€๋กœ ๋ฐ”๊พผ ํ›„, ํ˜„์žฌ ๋†’์ด๋ณด๋‹ค ์ž‘์œผ๋ฉด ์ด๋™ ๊ฐ€๋Šฅ

if (map[y][x] > map[ny][nx])
	```
์ฝ”๋“œ๋ฅผ ์ž…๋ ฅํ•˜์„ธ์š”
```dp[y][x] += down(ny, nx);

3. ์ฝ”๋“œ

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class DP_5 {
	static int dp[][], map[][];
	static int dx[] = { 0, 0, 1, -1 };
	static int dy[] = { 1, -1, 0, 0 };
	static int row, col;

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

		String s[] = br.readLine().split(" ");

		row = Integer.parseInt(s[0]);
		col = Integer.parseInt(s[1]);

		dp = new int[row][col];
		map = new int[row][col];

		for (int i = 0; i < row; i++) {
			s = br.readLine().split(" ");
			for (int j = 0; j < col; j++) {
				map[i][j] = Integer.parseInt(s[j]);
				dp[i][j] = -1;
			}
		}

		System.out.println(down(0, 0));
	}

	static int down(int y, int x) {
		if (y == row - 1 && x == col - 1)
			return 1;
		if (dp[y][x] != -1)
			return dp[y][x];

		dp[y][x] = 0;

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (ny >= row || nx >= col || ny < 0 || nx < 0)
				continue;
			if (map[y][x] > map[ny][nx])
				dp[y][x] += down(ny, nx);
		}
		
		return dp[y][x];
	}

}

4. ๊ฒฐ๊ณผ

์„ฑ๊ณต~

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ