[白俊]1520番下り坂
移動:上下左右にしか移動できません.
(0,0)->(m-1,n-1)に移動しようとします.
高さがもっと低いところに移動したいだけです.
このとき移動可能な[パス数]
トラブルシューティングプロセス
間違っています-->DPでも解けるみたい:PriorityQueueのDPで解ける
public class Main{
public static int m,n;
public static int[][] cache;
public static int[][] table;
public static Queue<int[]> q = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
// height를 기준으로 내림차순
return o2[2]-o1[2];
}
});
public static int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
public static int path =0;
public static void Setting() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
m = Integer.parseInt(st.nextToken());
n = Integer.parseInt(st.nextToken());
table = new int[m][n];
cache = new int[m][n];
for(int row=0;row<m;row++){
st = new StringTokenizer(br.readLine());
for(int col=0;col<n;col++)
table[row][col] = Integer.parseInt(st.nextToken());
}
// 0,0 칸 캐시를 1로 해야, 인접한 칸까지의 경로에 수가 더해진다.
cache[0][0]=1;
// PQ를 세팅한다.
// 첫 번째 줄은, (0,0)칸만 제외하고 넣어준다.
for(int col=1;col<n;col++)
q.add(new int[]{0,col,table[0][col]});
for(int row=1;row<m;row++){
for(int col=0;col<n;col++){
q.add(new int[]{row,col,table[row][col]});
}
}
}
public static void dp(){
int curH=0;
while(q.isEmpty()==false){
int[] cur = q.poll();
int path=0;
for(int dir=0;dir<dirs.length;dir++){
int y = cur[0]+dirs[dir][0];
int x = cur[1]+dirs[dir][1];
// 벗어나면 fail
if(y<0||x<0||y>=m||x>=n)continue;
// 더 높은 칸이면 path개수를 더한다.
if(table[y][x]>cur[2]) path+=cache[y][x];
}
//System.out.println(cur[0]+","+cur[1] +" : "+path);
// cache를 업데이트
cache[cur[0]][cur[1]]=path;
}
}
public static void main(String[] args) throws IOException{
Setting();
dp();
System.out.println(cache[m-1][n-1]);
}
}他の人の解題方法を見ました。DFS + DP
これは私の方法より効率的です.
簡単なDFSを使用して再帰的検索を行う場合、DFSを使用して遡及する方法は、非常に多くの場合に関連し、タイムアウトを引き起こす.
しかし、ここにDPを加えれば、時間を減らすことができます.
ここで、cache[y][x]は、そのセルを含むパスの個数を表す.
ある経路で[m,n]に到達すると,その経路に属するすべてのノードが[m,n]に到達する.
また,dfsについては,すべての経路が異なる経路であることを覚えればよい.(パスの設定が異なる)
dfsを使用するbacktrackでは、各パスで渡される値によって、現在のノードを含むパスの数がわかります.(絵を見ていると理解できるようです)
だから、この図で理解すればいいのです.
public class Main{
public static int m,n;
public static int[][] cache = new int[501][501];
public static int[][] table = new int[501][501];
public static int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
public static int path =0;
public static void Setting() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
m = Integer.parseInt(st.nextToken());
n = Integer.parseInt(st.nextToken());
for(int row=0;row<m;row++){
st = new StringTokenizer(br.readLine());
for(int col=0;col<n;col++)
table[row][col] = Integer.parseInt(st.nextToken());
}
// cache를 -1로 세팅한다. dfs를 통해서 cache에 0이 들어올 것도 존재함을 생각하라.
// dp는 왠만하면 -1로 세팅하고 시작한다.
for(int row=0;row<m;row++){
Arrays.fill(cache[row],-1);
}
}
public static int dfs(int y,int x){
//System.out.println(y+","+x);
if(x==n-1 &&y==m-1) return 1;
if(cache[y][x]!=-1) return cache[y][x];
int path =0;
for(int dir =0;dir<dirs.length;dir++){
int ny=y+dirs[dir][0];
int nx=x+dirs[dir][1];
// 범위를 넘으면 pass
if(ny<0||nx<0||ny>=m||nx>=n) continue;
// 더 낮은 곳이 아니면 pass
if(table[ny][nx]>=table[y][x])continue;
int temp = dfs(ny,nx);
path+=temp;
}
cache[y][x]=path;
return cache[y][x];
}
public static void main(String[] args) throws IOException{
Setting();
dfs(0,0);
System.out.println(cache[0][0]);
}
}Reference
この問題について([白俊]1520番下り坂), 我々は、より多くの情報をここで見つけました https://velog.io/@ynoolee/백준-1520번-내리막길テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol