백준 2186 C++ (문자판)

완전탐색은 쉽지않다. 헣

그래도 DP인거 알고 푸니까 어렵진 않았다.

완전탐색이라고 다 BFS, DFS는 아니다.

시간 제한	메모리 제한	정답률
2초	128MB	21.264%

문제

알파벳 대문자가 한 칸에 한 개씩 적혀있는 N×M 크기의 문자판이 있다. 편의상 모든 문자는 대문자라 생각하자. 예를 들어 아래와 같은 문자판을 보자.

K	A	K	T
X	E	A	S
Y	R	W	U
Z	B	Q	P

이 문자판의 한 칸(아무 칸이나 상관없음)에서 시작하여 움직이면서, 그 칸에 적혀 있는 문자들을 차례대로 모으면 하나의 단어를 만들 수 있다. 움직일 때는 상하좌우로 K개의 칸까지만 이동할 수 있다. 예를 들어 K=2일 때 아래의 그림의 가운데에서는 'X' 표시된 곳으로 이동할 수 있다.

		X
		X
X	X		X	X
		X
		X

반드시 한 칸 이상 이동을 해야 하고, 같은 자리에 머물러 있을 수 없다. 또, 같은 칸을 여러 번 방문할 수 있다.

이와 같은 문자판과 K, 그리고 하나의 영단어가 주어졌을 때, 이와 같은 영단어를 만들 수 있는 경로가 총 몇 개 존재하는지 알아내는 프로그램을 작성하시오.

위의 예에서 영단어가 BREAK인 경우에는 다음과 같이 3개의 경로가 존재한다. 앞의 수는 행 번호, 뒤의 수는 열 번호를 나타낸다.

(4, 2) (3, 2) (2, 2) (1, 2) (1, 1)
(4, 2) (3, 2) (2, 2) (1, 2) (1, 3)
(4, 2) (3, 2) (2, 2) (2, 3) (1, 3)

입력

첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 영단어가 주어진다. 모든 문자들은 알파벳 대문자이며, 공백 없이 주어진다.

출력

첫째 줄에 경로의 개수를 출력한다. 이 값은 int 범위이다.

핵심

BFS나 DFS로 순회하면서 구하면 금방 구해짐(본인은 BFS로 처음에 시도했음). 문제는 시간초과됌;;
그걸 방지하기 위해 DP를 쓸거고, 메모이제이션을 하면 해결가능
dp[a][b][level] : 맨 끝 문자에서 좌표 (a,b)로 가는 경로 수의 합. 이때, (a,b)는 level번째 문자(alphabet처럼 a가 첫번째일 수도 있고 5번째일 수도 있으니 체크한다는 뜻)

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>


using namespace std;

int n, m, k, ans;
char matrix[100][100];
int dp[100][100][100];
string input;


void clear_dp(){
    for(int i=0;i<100;i++){
        for(int j=0;j<100;j++){
            for(int l=0;l<100;l++)
            dp[j][i][l] = -1;
        }
    }
}


int rec(int a, int b, int level){
    if(dp[a][b][level] != -1) return dp[a][b][level];
    if(level >= input.size()-1) return 1;
     
    
    int ret = 0;
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    
    
    for(int d=0;d<4;d++){
        for(int i=1;i<=k;i++){
            pair<int, int> next = { a + dx[d]*i, b + dy[d]*i };
            if(next.first < 0 || next.first >= m) continue;
            if(next.second < 0 || next.second >= n) continue;
                
                
            if(matrix[next.first][next.second] == input[level + 1]){
                ret += rec(next.first, next.second, level + 1);
                
            }
        }
    }
    
    dp[a][b][level] = ret;
    return ret;
}


int main(int argc, char* argv[]) {
	ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n >> m >> k;
    
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> matrix[j][i];
        }
    }
    
    cin >> input;
    
    
    clear_dp();
    
    //finding startig points
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(matrix[j][i] == input[0]){
                ans += rec(j, i, 0);
                
            }
        }
    }
    
    cout << ans << '\n';
    
	return 0;
}