[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. ๊ฒฐ๊ณผ
์ฑ๊ณต~
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ([Algorithm] ๐ฃ๏ธ๋ฐฑ์ค 1520 ๋ด๋ฆฌ๋ง ๊ธธ), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@kha0318/Algorithm-๋ฐฑ์ค-1520-๋ด๋ฆฌ๋ง-๊ธธ์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ ์ธ ๋ฐ๊ฒฌ์ ์ ๋ (Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค