Memo
테트로미노의 경우도 최악의 경우에는 가로 및 세로가 500 by 500으로 고정됨
우선 테트로미노의 최악의 경우는 각 칸당 4번씩 DFS를 호출하게 되고, 최악에는 500 by 500이 있으므로 약 회의 호출로 마무리 되므로 브루트 포스로도 풀림
이 문제도 처음에는 DP가 필요한지 몰랐고, 브루트 포스로 푸는 것이 가능하지 않을까 생각을 해봄 (DFS를 통해 가능한 경우를 모두 세는...)
테트로미노의 경우는 브루트 포스로 풀더라도 한 칸당 최대 함수 호출 회수는 4회였지만, 이 문제는 함수 호출 최대 횟수는 갈 곳이 없어지거나 종착점 도착하기 전까지므로 상당히 높은 편
대충 계산해서 최악에는 얼추 정도...? 이고, 문제에서 요구하는 시간은 2초므로 약 2억번의 연산이 가능하다고 쳐도 위 경우는 커버가 안 되는 것을 짐작 가능
시작 ~ 종착까지 가는 경우를 하나씩 일일이 세는 것이 아니라 Memoization을 통해서 탐색 수를 줄일 수 있다는 것을 알았고, DFS + DP로 풀 수 있다는 것을 알게됨
처음에는 방문 확인 용도의 컨테이너와 Memoization 용도의 컨테이너를 따로 두었지만, Memoization에 기록된 값이 있다면 이미 방문을 해본 것이므로 그 값을 그대로 차용
1.
Memoization이 방문 확인 용도를 겸임하므로 초기 값을 무엇을 줄지 고민 → 경로가 없는 경우는 0이 될 수도 있으므로 방문을 하지 않았다는 의미는 음수로 주면 됨
2.
중복 노드에 대해서 방문 확인을 재차 해야하는가? (즉, 방문 했던 노드를 다시 방문할 수 있도록 풀어주어 다시 탐색을 해줘야 하는가?) → 이미 해당 노드는 이전 노드들의 누적 경우의 수가 담겨 있으므로 그대로 이용을 해도 됨 (따라서 다시 탐색할 필요가 없음)
유의할 점
1.
내 경우는 끝에서부터 탐색을 시작하므로 현재 탐색 노드와 다음 방문 노드의 값을 비교 시 현재 탐색 노드의 값이 작아야함
2.
시작점에 도달 시 1을 리턴해주는 구문이 필요 (그렇지 않으면 0으로만 초기화 되고 결과 값도 0으로 나옴)
3.
탐색이 끝나고 리턴 받은 값은 현재 Memoization 값에 그 경우의 수가 누적됨
Code
제출 날짜
@2/17/2021
메모리
4132 KB
시간
24 ms
#include <iostream>
#include <vector>
using pii = std::pair<int, int>;
int g_row;
int g_col;
std::vector<std::vector<int>> g_map;
std::vector<std::vector<int>> g_memoi;
std::vector<pii> g_dir;
void pre_setting(void)
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
}
void input_action(void)
{
std::cin >> g_row >> g_col;
g_map = std::vector<std::vector<int>>(g_row, std::vector<int>(g_col, 0));
g_memoi = std::vector<std::vector<int>>(g_row, std::vector<int>(g_col, -1));
g_dir = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
for (auto &i : g_map)
for (auto &j : i)
std::cin >> j;
}
int logic(int row, int col)
{
int n_row;
int n_col;
if (row == 0 && col == 0)
return (1);
if (g_memoi[row][col] == -1)
{
g_memoi[row][col] = 0;
for (auto &i : g_dir)
{
n_row = row + i.first;
n_col = col + i.second;
if (n_row < g_row && n_row >= 0 && n_col < g_col && n_col >= 0 &&
g_map[row][col] < g_map[n_row][n_col])
g_memoi[row][col] += logic(n_row, n_col);
}
}
return (g_memoi[row][col]);
}
void output_action(void)
{
std::cout << logic(g_row - 1, g_col - 1);
}
void solution(void)
{
input_action();
output_action();
}
int main(void)
{
pre_setting();
solution();
return (0);
}
C++
복사