Search

내리막 길

Created
2021/03/23 01:58
문제 번호
1520
카테고리
그래프
DFS
DP

Memo

문제를 보면서 경로 탐색이 필요한데다가 가로 및 세로 범위 때문에 테트로미노가 가장 먼저 생각남
테트로미노의 경우도 최악의 경우에는 가로 및 세로가 500 by 500으로 고정됨
우선 테트로미노의 최악의 경우는 각 칸당 4번씩 DFS를 호출하게 되고, 최악에는 500 by 500이 있으므로 약 100,000100,000회의 호출로 마무리 되므로 브루트 포스로도 풀림
이 문제도 처음에는 DP가 필요한지 몰랐고, 브루트 포스로 푸는 것이 가능하지 않을까 생각을 해봄 (DFS를 통해 가능한 경우를 모두 세는...)
테트로미노의 경우는 브루트 포스로 풀더라도 한 칸당 최대 함수 호출 회수는 4회였지만, 이 문제는 함수 호출 최대 횟수는 갈 곳이 없어지거나 종착점 도착하기 전까지므로 상당히 높은 편
대충 계산해서 최악에는 얼추 45004^{500}정도...? 210002^{1000}이고, 문제에서 요구하는 시간은 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++