풀이
문제를 보고 처음 생각했던건 BFS 풀이였다.
(단순히 DFS로 계산하면 시간복잡도는 nm 각 지점에서 nm 번 탐색이 이뤄질 수 있으므로 500^4 = 624억 이므로 시간초과가 발생한다)
dp[x][y]는 (0,0) 에서 (x,y)로 갈 수 있는 경로의 수로 정했고, BFS를 하면서 갈 수 있는 경로에 +1 을 해주었다. 그리고 처음 방문하는 지역은 큐에 추가하여 경로탐색을 이어갈 수 있도록 했다.
하지만 특정 지점에서 +1 이 추가되기 전에 추가 경로탐색이 시작되면 뒤늦게 추가된 +1은 경로에 반영되지 않는다는 문제점이 존재했다.
해당 문제점을 잘 풀이해준 글을 참고하시길 바란다.
https://limepencil.tistory.com/5
그래서 단순 큐가 아닌, 해당 문제가 발생하지 않도록하는 순서 또는 규칙이 필요했다.
해당 문제에서는 특별하게 높이 순서에 따라 높은 지역부터 탐색할 경우 문제가 해결된다.
BFS + PQ 로 해결하기 위해서는, 특정한 기준으로 이럭헤 뒤 늦게 최신화되는 문제를 해결할 수 있어야한다.
시간복잡도 비교
기본적인 DFS 방식 -> 500^4 = 6*10^10
한 지점에서 연산은 각 방향으로 4번 발생할 수 있으므로
4500500 = 10^6
import java.io.*;
import java.util.*;
public class Main {
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static class Node {
int x;
int y;
int hei ;
public Node (int x,int y,int hei){
this.x = x;
this.y = y;
this.hei = hei;
}
}
public static void main(String[] args) throws IOException {
String[] inp = br.readLine().split(" ");
int x = Integer.parseInt(inp[0]); // 세로
int y = Integer.parseInt(inp[1]); // 가로
int[][] board = new int[x+1][y+1];
boolean[][] visited = new boolean[x+1][y+1];
int[][] cnt = new int[x+1][y+1];
for(int i=0;i<x;i++){
inp = br.readLine().split(" ");
for(int j=0;j<y;j++){
board[i][j] = Integer.parseInt(inp[j]);
}
}
PriorityQueue<Node> pq = new PriorityQueue<Node>(new Comparator<Node>(){
@Override
public int compare(Node a,Node b){
return -(a.hei - b.hei);
}
});
pq.add(new Node(0,0,board[0][0]));
int[] dy = {1,-1,0,0};
int[] dx = {0,0,1,-1};
cnt[0][0] = 1;
while(!pq.isEmpty()){
Node cur = pq.poll();
for(int i=0;i<4;i++){
int nx = dx[i] + cur.x;
int ny = dy[i] + cur.y;
if(nx <0 || nx >= x || ny <0 || ny >= y){
continue;
}
if(board[cur.x][cur.y] <= board[nx][ny]){
continue;
}
cnt[nx][ny] += cnt[cur.x][cur.y];
if(!visited[nx][ny]){
visited[nx][ny] = true;
pq.add(new Node(nx,ny, board[nx][ny]));
}
}
}
System.out.println(cnt[x-1][y-1]);
}
}풀이2 (DFS + DP)
대부분 이렇게 푼것 같다.
dp[x][y] 를 x,y로 부터 목적지까지 도착하기 위한 경로의 수로 정한다.
이렇게 정해야 재귀함수를 통해 Bottom-up 으로 문제를 해결할 수 있다.
놓친점 1
dp의 초깃값을 0으로 설정하면 결과가 0인 DFS는 반복해서 수행되므로 메모리초과가 발생할 수 있다.
-1로 설정해주자.
시간복잡도 개선
DP를 사용하면 기존 500^4 에서
하나의 지점에서 4가지 연산이 최대 1번씩 이뤄날 수 있으므로
4500500 = 10^6 으로 개선된다,
import java.io.*;
import java.util.*;
public class Main {
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static class Node {
int x;
int y;
public Node (int x,int y){
this.x = x;
this.y = y;
}
}
static int x;
static int y;
public static void main(String[] args) throws IOException {
String[] inp = br.readLine().split(" ");
x = Integer.parseInt(inp[0]); // 세로
y = Integer.parseInt(inp[1]); // 가로
int[][] board = new int[x+1][y+1];
boolean[][] visited = new boolean[x+1][y+1];
int[][] dp = new int[x+1][y+1];
for(int i=0;i<x;i++){
inp = br.readLine().split(" ");
for(int j=0;j<y;j++){
board[i][j] = Integer.parseInt(inp[j]);
dp[i][j] = -1;
}
}
int ans = dfs(new Node(0,0),board,dp);
System.out.println(ans);
}
public static int dfs(Node cur, int[][] board, int[][] dp){
if(cur.x == x-1 && cur.y == y-1){
return 1;
}
int[] dy = {1,-1,0,0};
int[] dx = {0,0,1,-1};
int cnt = 0;
for(int i=0;i<4;i++){
int nx = dx[i]+cur.x;
int ny = dy[i] + cur.y;
if(nx < 0 || nx >=x || ny <0 || ny>= y){
continue;
}
if(board[nx][ny] < board[cur.x][cur.y]){
// 시작
if(dp[nx][ny] == -1){
// 기존 데이터가 없으면 DFS 진행
dp[nx][ny] = dfs(new Node(nx, ny), board, dp);
}
cnt += dp[nx][ny];
}
}
return cnt;
}
}
