문제 :
https://www.acmicpc.net/problem/1520
접근 1:
- BFS 로 결과 지점까지 도달하면 결과값 + 1
- Queue 가 빌 때까지 실행 후 출력
- 메모리 초과로 불가
접근 2:
- DP 와 DFS 를 이용하여 정답을 카운트
- 정답 지점까지 도달한 후, 시작 지점으로 돌아오면서 count 를 증가
- 시작 지점에 도달하면 count를 정답으로 출력
코드 구현 :
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
private static int[][] map;
private static int[][] dp;
private static final Position[] dir = {
new Position(0,1), new Position(1,0), new Position(0,-1), new Position(-1,0)
};
private static class Position{
private int x;
private int y;
public Position(int x, int y){
this.x = x;
this.y = y;
}
public int getX() {
return this.x;
}
public int getY() {
return this.y;
}
}
public static int dfs(Position now) {
if (now.getX() == map.length-1 && now.getY() == map[0].length-1) return 1;
if(dp[now.getX()][now.getY()] >= 0) return dp[now.getX()][now.getY()];
//방문 기록
dp[now.getX()][now.getY()] = 0;
int nx, ny;
for (Position p : dir) {
nx = now.getX() + p.getX();
ny = now.getY() + p.getY();
if (nx < 0 || ny < 0 || nx > map.length-1 || ny > map[0].length-1) continue;
if (map[now.getX()][now.getY()] <= map[nx][ny]) continue;
dp[now.getX()][now.getY()] += dfs(new Position(nx, ny));
}
return dp[now.getX()][now.getY()];
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = br.readLine().split(" ");
int n = Integer.parseInt(inputs[0]);
int m = Integer.parseInt(inputs[1]);
map = new int[n][m];
dp = new int[n][m];
for (int i=0 ; i < n ; i++) {
String[] temp = br.readLine().split(" ");
for (int j=0; j < m; j++) {
map[i][j] = Integer.parseInt(temp[j]);
dp[i][j] = -1;
}
}
System.out.println(dfs(new Position(0, 0)));
}
}
'JAVA > Coding Test' 카테고리의 다른 글
[JAVA] 백준 2688 줄어들지 않아_DP (0) | 2024.06.26 |
---|---|
백준 9465 스티커_DP (0) | 2024.06.26 |
[JAVA] 백준 2193 이친수_DP (0) | 2024.06.24 |
[JAVA] 백준 2156 포도주_DP (0) | 2024.06.24 |
[JAVA] 백준 2011 암호코드 _DP (0) | 2024.06.21 |