2186번: 문자판

시간초과 해결하는데 상당히 힘들었던 문제입니다.

백트래킹과 비슷한 방식을 사용하는데 DP방식과 섞는 느낌?으로 DFS를 구성하면 답을 구할 수 있습니다.

#include <iostream>
#include <string>
#include <cstring>
 
typedef struct {
    int y, x;
} dif;
 
dif dir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
 
int visited[101][101][101] = { 0 };
std::string map[101];
std::string result;
int row, col, term;
 
int DFS(int y, int x, int idx) {
    if(visited[y][x][idx - 1] != -1) {
        return visited[y][x][idx - 1];
    }
    visited[y][x][idx - 1] = 0;
 
    if (idx == result.size()) {
        visited[y][x][idx - 1] = 1;
        return visited[y][x][idx - 1];
    }
 
    for(int i = 0; i < 4; i++) {
        int tempY = y;
        int tempX = x;
        for (int j = 0; j < term; j++) {
            tempY += dir[i].y;
            tempX += dir[i].x;
 
            if(tempY < 0 || tempY >= row || tempX < 0 || tempX >= col) { break; }
            if(result[idx] != map[tempY][tempX]) { continue; }
            visited[y][x][idx - 1] += DFS(tempY, tempX, idx + 1);
        }
    }
    return visited[y][x][idx - 1];
}
 
int main(void) {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
 
    std::cin >> row >> col >> term;
 
    for (int i = 0; i < row; i++) {
        std::cin >> map[i];
    }
    std::cin >> result;
 
    int sum = 0;
    memset(visited, -1, sizeof(visited));
    for(int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if(result[0] != map[i][j]) { continue; }
            sum += DFS(i, j, 1);
        }
    }
 
    std::cout << sum << "\n";
    return 0;
}