[BaekJoon] 백준 1520번 _ 내리막 길 for JAVA _ DFS + DP 알고리즘

 

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

1520번: 내리막 길

 

 

 

문제

 

 

 

---

 

DFS 썼다.

 

 

 

근디 걍 DFS만 쓰면 시간 초과가 된다.

 

 

 

 

시간 초과된 코드(실패)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Baek1520 { // 내리막길 DFS
	public static int M, N;
	public static int map[][];
	public static int visited[][];
	public static int dx[] = {1, -1, 0, 0};
	public static int dy[] = {0, 0, 1, -1};
	public static int count = 0;
	
	public static void main(String[] args) 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());
		
		map = new int[M][N];
		visited = new int[M][N];
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		visited[0][0] = 1;
		dfs(0, 0);
		System.out.println(count);
		
	}
	
	public static void dfs(int x, int y) {
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx <= -1 || nx >= M || ny <= -1 || ny >= N) continue;
			if(nx == M-1 && ny == N-1) count++;
			
			if(map[nx][ny] < map[x][y] && map[nx][ny] != 1) {
				visited[nx][ny] = 1;
				dfs(nx, ny);
				visited[nx][ny] = 0;
			}
		}
	
	}

}

 

 

 

 

그래서 DP같은걸 이용해 효율을 높여야한다.

 

 

 

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Baek1520 { // 내리막길 DFS
	public static int M, N;
	public static int map[][];
	public static int visited[][];
	public static int dx[] = {1, -1, 0, 0};
	public static int dy[] = {0, 0, 1, -1};
	public static int count = 0;
	
	public static void main(String[] args) 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());
		
		map = new int[M][N];
		visited = new int[M][N];
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				visited[i][j] = -1;
			}
		}
		
		
		System.out.println(dfs(0, 0));
		
	}
	
	public static int dfs(int x, int y) {
		if(x == M-1 && y == N-1) return 1; // 제일 뒤까지 탐색했다면 +1
		if(visited[x][y] != -1) return visited[x][y]; // 이미 들렀다면(0이라면) 걍 지나가
		else {
			visited[x][y] = 0; // 방문처리
			for(int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if(nx <= -1 || nx >= M || ny <= -1 || ny >= N) continue;
				
				if(map[nx][ny] < map[x][y]) {
					visited[x][y] += dfs(nx, ny);
				}
			}
		}
		
		return visited[x][y]; // 맨 마지막에 도달했을 때에만 +1씩 갈겨왔으므로 얘를 출력하면 된다.
	}

}

 

 

 

이제 dp를 잘 활용해야겠다~