앞서 백트래킹 로직을 DP 로직으로 변경하는 기법을 소개한 바 있다. 원문 링크
해당 게시물에서 예시로 들었던 문제보다 어려우면서도 이를 적용하기 좋은 문제가 있어 풀이 과정을 보이겠다.
시작 지점(0, 0)으로부터 높이가 낮은 지점으로 이동해 가면서 도착 지점(M-1, N-1)에 도달하는 경우의 수를 구한다. 이번에도 다음과 같은 순서로 풀이한다.
- 완전탐색
- 점화식 및 테이블 구성
- Top-down DP 로직으로 변경
1. 완전탐색
DFS를 사용해 완전탐색 로직을 다음과 같이 구현했다.
#include <bits/stdc++.h>
using namespace std;
int M, N;
int dr[4] = { 0, -1, 0, 1 };
int dc[4] = { -1, 0, 1, 0 };
vector<vector<int>> height;
inline bool CheckValidPoint(int r, int c);
int DFS(int r, int c);
int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> M >> N;
height.resize(M, vector<int>(N));
for (int r = 0; r < M; r++)
for (int c = 0; c < N; c++)
cin >> height[r][c];
cout << DFS(0, 0);
return 0;
}
inline bool CheckValidPoint(int r, int c) {
return (0 <= r && r < M && 0 <= c && c < N);
}
int DFS(int r, int c) {
if (r == M - 1 && c == N - 1)
return 1;
int ret = 0;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (CheckValidPoint(nr, nc) && height[nr][nc] < height[r][c])
ret += DFS(nr, nc);
}
return ret;
}각각의 지점에서 상하좌우 방향을 탐색하며 좌표 값이 유효한지, 해당 좌표의 높이가 더 낮은지를 검사하고 재귀 호출의 깊이를 늘려 나간다. 지수적 시간 복잡도를 갖기 때문에 이대로 제출하면 당연히 시간초과가 발생한다.
2. 점화식 및 테이블 구성
재귀 함수의 매개변수를 인덱스로, 반환 값을 저장 값으로 갖는 테이블을 구성하자.
...
#define NONE -1
...
vector<vector<int>> table; // table[row][column]
...
table.resize(M, vector<int>(N, NONE));
...일단 테이블을 구성하고 나면 우리가 테이블의 생김새에 맞추어 점화식을 구성할 수 있다. 다시 한번 강조하지만 이 방법이 획기적인 이유는 점화식을 떠올리고 점화식에 맞는 테이블을 구성하는 일반적인 DP의 풀이 과정이 아니라, 역으로 테이블을 구성하고 이에 맞춰 점화식을 떠올릴 수 있기 때문이다.
이 테이블의 인덱스는 지도상의 특정 좌표를 의미하고, 저장된 값은 해당 좌표에서 목적지로 이동하는 길의 개수를 의미한다.
3. Top-down DP 로직으로 변경
수정된 DFS() 함수의 코드는 다음과 같다.
int DFS(int r, int c) {
if (r == M - 1 && c == N - 1)
return 1;
int& ret = table[r][c];
if (ret != NONE)
return ret;
ret = 0;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (CheckValidPoint(nr, nc) && height[nr][nc] < height[r][c])
ret += DFS(nr, nc);
}
return ret;
}아래 기존의 DFS() 함수 코드와 비교해 보자.
int DFS(int r, int c) {
if (r == M - 1 && c == N - 1)
return 1;
int ret = 0;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (CheckValidPoint(nr, nc) && height[nr][nc] < height[r][c])
ret += DFS(nr, nc);
}
return ret;
}경로의 개수는 0개 이상이므로 테이블에 절대로 가질 수 없는 값인 -1(NONE)을 넣어놓고, 이를 사용해 메모이제이션 여부를 검사한다. 이미 메모이제이션이 되어 있다면 그대로 사용하고(if (ret) return ret;), 그렇지 않다면 ret = 0으로 경로의 개수를 초기화한 다음 기존의 로직을 그대로 수행한다.
전체 코드
#include <bits/stdc++.h>
using namespace std;
#define NONE -1
int M, N;
int dr[4] = { 0, -1, 0, 1 };
int dc[4] = { -1, 0, 1, 0 };
vector<vector<int>> height;
vector<vector<int>> table;
inline bool CheckValidPoint(int r, int c);
int DFS(int r, int c);
int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> M >> N;
table.resize(M, vector<int>(N, NONE));
height.resize(M, vector<int>(N));
for (int r = 0; r < M; r++)
for (int c = 0; c < N; c++)
cin >> height[r][c];
cout << DFS(0, 0);
return 0;
}
inline bool CheckValidPoint(int r, int c) {
return (0 <= r && r < M && 0 <= c && c < N);
}
int DFS(int r, int c) {
if (r == M - 1 && c == N - 1)
return 1;
int& ret = table[r][c];
if (ret != NONE)
return ret;
ret = 0;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (CheckValidPoint(nr, nc) && height[nr][nc] < height[r][c])
ret += DFS(nr, nc);
}
return ret;
}