[백준] 1520번 내리막 길 (자바 풀이)

문제

https://www.acmicpc.net/problem/1520

1520번: 내리막 길

풀이

처음 문제를 봤을 땐 DFS를 사용하면 간단하게 풀릴 것 같았다. 하지만 결과는 시간초과.....

 

이 문제는 단순히 DFS만을 사용하면 시간초과가 발생한다. DFS와 DP를 섞어서 사용해야 한다. 만약 DFS를 통해 모든 길을 탐색하던 도중 이미 탐색해서 경로를 계산한 좌표를 만난다면 굳이 다시 탐색을 할 필요는 없다. 따라서 이를 미리 저장해놓고 사용하면 된다.

코드

import java.io.*; import java.util.*; public class Main{ static int N,M; static int map[][]; static int dx[] = {-1,1,0,0}; static int dy[] = {0,0,-1,1}; static int dp[][]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); map = new int[N][M]; dp = new int[N][M]; for(int i=0; i=N || ny >= M) continue; if(map[nx][ny] < map[x][y]) { dp[x][y] += dfs(nx,ny); } } return dp[x][y]; } }

결과