BOJ 2186 : 문자판 [C++]

2186번: 문자판

 

처음에는 그냥 DFS 돌리면 되지 않을까?라고 생각했는데 시간초과가 났다;;

 

메모이제이션을 적용

 

dp[i][j][k] : (i, j)칸이 주어진 영단어의 k번째 알파벳으로 위치할 수 있는 경우의 수

 

메모이제이션을 적용하고도 계속 시간초과가 나서 왜 그런가 고민하다가 질문 게시판을 확인했는데,

dp 배열을 -1로 초기화하지 않은 것이 문제였다.

 

dp 배열을 0으로 초기화하면 생기는 문제

• (i, j)칸이 주어진 영단어의 k번째 알파벳이 될 수 없는 경우에는 0이 dp[i][j][k]에 들어간다.
• 이때 dp 배열을 0으로 초기화했다면, 이 칸이 방문하지 않은 칸인지 방문했는데도 불가능해서 0인지 구분할 수가 없게 된다.

 

코드

#include <iostream>

int N, M, K;
std::string word;
char grid[101][101];
int dp[101][101][81];

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

int dfs(int x, int y, int index) {
    if (index == word.size() - 1) {
        return dp[x][y][index] = 1;
    }

    if (dp[x][y][index] != -1) {
        return dp[x][y][index];
    }

    dp[x][y][index] = 0;
    for (int i = 0; i < 4; i++) {
        for (int j = 1; j < K + 1; j++) {
            int nx = x + dx[i] * j;
            int ny = y + dy[i] * j;

            if (nx < 0 || nx > N - 1 || ny < 0 || ny > M - 1) {
                break;
            }
            if (word[index + 1] == grid[nx][ny]) {
                dp[x][y][index] += dfs(nx, ny, index + 1);
            }
        }
    }

    return dp[x][y][index];
}

int main() {
    std::cin.tie(NULL);
    std::ios::sync_with_stdio(false);

    std::cin >> N >> M >> K;

    std::string row;
    for (int i = 0; i < N; i++) {
        std::cin >> row;
        for (int j = 0; j < M; j++) {
            grid[i][j] = row[j];
        }
    }

    std::cin >> word;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            for (int k = 0; k < word.size(); k++) {
                dp[i][j][k] = -1;
            }
        }
    }

    int answer = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (grid[i][j] == word[0]) {
                answer += dfs(i, j, 0);
            }
        }
    }

    std::cout << answer << "\n";

    return 0;
}