Dynamic Programming이 섞인 DFS⛓️ - 내리막길, 욕심쟁이 판다🐼

▶ 유형

• 그냥 DFS를 돌렸을 때 엄청난 연산량(재귀호출)로 인해 시간초과, 스택초과, 메모리초과 등을 야기할 수 있는 문제.
• 이전 경우의 수가 현재 경우에 반영되는 DP를 활용해야 하는 유형이다.

DFS는 깊이 우선 탐색으로 현재 자기 시점에서 다음 지점으로 접근하는 알고리즘인데, 재귀호출 시 이미 방문한 경우도 해당 재귀 분기에서는 방문하지 않은 상태로 접근하기 때문에 map이 크거나, 그래프의 depth가 깊으면 요구하는 시간, 메모리를 초과할 수 있다.

 

피보나치가 제일 대표적인 예시인데, 아래 그림을 보자

graph TD;
    A(fib5) --> B(fib4)
    A --> C(fib3)
    B --> D(fib3)
    B --> E(fib2)
    C --> F(fib2)
    C --> G(fib1)
    D --> H(fib1)
    E --> I(fib1)
    F --> J(fib2)
    F --> K(fib1)
    G --> L(fib1)
    H --> M(fib4)
    H --> N(fib3)
    M --> O(fib2)
    M --> P(fib1)
    N --> Q(fib2)
    N --> R(fib1)
    O --> S(fib1)
    Q --> T(fib1)

leaf노드로 갈 수록 중복된 함수들을 계속 호출하는 것을 볼 수 있다.

이 중복호출을 줄이는 방법은 재귀호출 전 이전에 연산된 값이 있다면 그 값을 참조해서 호출 횟수를 줄이는 것인데 이걸 메모이제이션이라고 부른다. 

DP의 가장 무난한 접근방법이 이전에 계산한 값을 활용해서 다음 값을 도출하는 것이므로 지금 상황에 사용할 수 있을 것이다.

대상 문제로 백준 1520번의 내리막길 문제를 풀어보자.

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

1520번: 내리막 길

▶ 전략

먼저 DP를 사용하지 않았을 때의 코드다.

import java.io.*;
import java.util.*;

class Main {
	static int[] di = { -1, 0, 1, 0 };
	static int[] dj = { 0, 1, 0, -1 };
	static int n, m;
	static int cnt = 0;
	static int[][] map;
	static boolean[][] v;

	public static void dfs(int ci, int cj) {
		if (ci == n - 1 && cj == m - 1) {
			cnt++;
			return;
		}

		boolean fail = true;
		for (int i = 0; i < 4; i++) {
			int ni = di[i] + ci;
			int nj = dj[i] + cj;
			if (isValid(ci, cj, ni, nj)) {
				fail = false;
				v[ni][nj] = true;
				dfs(ni, nj);
				v[ni][nj] = false;
			}
		}
		if (fail)
			return;

	}

	public static boolean isValid(int ci, int cj, int ni, int nj) {
		return ni < n && nj < m && ni >= 0 && nj >= 0 && !v[ni][nj] && map[ci][cj] > map[ni][nj];
	}

	public static void main(String args[]) throws Exception {
		System.setIn(new FileInputStream("res/input.txt"));
		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];
		v = new boolean[n][m];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < m; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		v[0][0] = true;
		dfs(0, 0);
		System.out.println(cnt);
	}
}

전형적인 DFS코드인데, 이걸로 제출하면 시간초과가 난다. 왜 날까?

입력을 확인해야된다.

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

map의 최대 크기가 500x500이고, 각 칸에서 4방향으로 재귀탐색을 한다. 25000개의 칸에서 4방향 재귀탐색인데, 그럼 재귀는 최대 4^25000번 돌 수 있게된다. 4^20이 대략 1조이니까 말도 안되게 큰 숫자가 나온다. 당연히 재귀스택이 터진다고봐도 되고, 스택이 터지지않더라도 엄청난 시간이 걸린다. 

 

그럼 어떻게 풀어야할까? 

갈 수 있는 내리막길 경우의 수를 각 칸 dp[ci][cj] 에 담으면서 이동하는 방법이 있다. 

class Main {
	static int[] di = { -1, 0, 1, 0 };
	static int[] dj = { 0, 1, 0, -1 };
	static int n, m;
	static int[][] map;
	static int[][] dp;

	public static int dfs(int ci, int cj) {
		if (ci == n - 1 && cj == m - 1) {
			return 1;
		}
		if (dp[ci][cj] != -1)
			return dp[ci][cj]; // 방문했으니까 계산하지않고 반환한다.
		dp[ci][cj] = 0; // 방문처리
		for (int i = 0; i < 4; i++) {
			int ni = di[i] + ci;
			int nj = dj[i] + cj;
			if (isValid(ci, cj, ni, nj)) {
				dp[ci][cj] += dfs(ni, nj);
			}
		}
		return dp[ci][cj]; // 재귀호출을 다 하고나서 반환해준다.
	}

	public static boolean isValid(int ci, int cj, int ni, int nj) {
		return ni < n && nj < m && ni >= 0 && nj >= 0 && map[ci][cj] > map[ni][nj];
	}

	public static void main(String args[]) throws Exception {
		System.setIn(new FileInputStream("res/input.txt"));
		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; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < m; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				dp[i][j] = -1;
			}
		}
		dfs(0, 0);
		System.out.println(dp[0][0]); // 이러면 최종적으로는 dp[0][0]에 값이 누적되어있을 것이다.
	}
}

그냥 코드만 보면 이걸로 뭐 단축이 되겠냐 싶은데, 상태공간트리로 비교하면 확 달라진다.

graph TD;
    A((0,0))
    A --> B((1,0))
    B --> C((2,0))
    A --> D((0,1))
    D --> E((1,1))
    E --> F((1,2))
    F --> G((1,3))
    G --> H((2,3))
    H --> I((3,3))
    I --> J((3,4))
    J --> K((3,5))
    K --> L((3,6))
    L --> M((3,7))

이게 DP배열을 활용할때의 상태공간 트리이고

아래가 DP배열 없이 호출할 때의 상태공간 트리다.

graph TD;
    A((0,0))
    A --> B((1,0))
    B --> C((2,0))
    C --> D((3,0))
    B --> E((1,1))
    E --> F((2,1))
    F --> G((3,1))
    E --> H((1,2))
    H --> I((2,2))
    I --> J((3,2))
    H --> K((1,3))
    K --> L((2,3))
    L --> M((3,3))
    K --> N((0,3))
    N --> O((1,3))
    O --> P((2,3))
    N --> Q((0,4))
    Q --> R((1,4))
    R --> S((2,4))
    Q --> T((0,5))
    T --> U((1,5))
    U --> V((2,5))
    T --> W((0,6))
    W --> X((1,6))
    X --> Y((2,6))
    W --> Z((0,7))

똑같이 (3,7) 을 찾아가는 코드인데,  엄청난 차이가 있다, DFS만 사용한 코드는 심지어 트리 상에 나오지도 않았다. 이 차이를 활용하면 더 깊이 들어가는 걸 중간에 연산값을 불러와 끊어버릴 수 있게되므로 엄청난 재귀호출을 막을 수 있게된다. 비슷한 문제로 욕심쟁이 판다문제가 있다.

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

1937번: 욕심쟁이 판다

내리막길과 거의 비슷한 유형인데 좀 더 복잡하다. base case가 더이상 뻗어나가면 안되는 게 조건이고, 결과값으로는 가장 depth가 깊은 경우의 depth를 출력해야한다. 

그럼 이번에는 최대 길이가 출발지인 dp[ci][cj]에 저장되도록 설계하면 된다. 이동할 때마다 한칸씩 늘려서 들어가면 된다.

import java.io.*;
import java.util.*;

class Main {
	static int[] di = { -1, 0, 1, 0 };
	static int[] dj = { 0, 1, 0, -1 };
	static int n;
	static int[][] map;
	static int[][] dp;
	static int max = -1;

	public static int dfs(int ci, int cj) {
		if (dp[ci][cj] != -1)
			return dp[ci][cj]; // 방문했으니까 계산하지않고 반환한다.
		dp[ci][cj] = 1; // 방문처리
		for (int i = 0; i < 4; i++) {
	        int ni = di[i] + ci;
	        int nj = dj[i] + cj;
	        if (isValid(ci, cj, ni, nj)) {
	            dp[ci][cj] = Math.max(dp[ci][cj], 1 + dfs(ni, nj)); // 탐색을 진행하고 최댓값을 저장한다.
	        }
	    }
	    return dp[ci][cj];
	}

	public static boolean isValid(int ci, int cj, int ni, int nj) {
		return ni < n && nj < n && ni >= 0 && nj >= 0 && map[ci][cj] < map[ni][nj];
	}

	public static void main(String args[]) throws Exception {
		System.setIn(new FileInputStream("res/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		n = Integer.parseInt(st.nextToken());
		map = new int[n][n];
		dp = new int[n][n];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				dp[i][j] = -1;
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				dfs(i, j);
				max = Math.max(max, dp[i][j]);
			}
		}
		System.out.println(max);
	}
}

거의 비슷한 문제였지만 base case 설정하는 게 약간 달라서 풀어볼 만한 문제였다.

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^