Baekjoon 2186번 문자판

문제

https://www.acmicpc.net/problem/2186

걸린 시간

-

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int n, m, k;
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
string word;
vector<string> plate;
vector<vector<vector<int>>> cache;

int solve(int y, int x, int idx){
    // 기저 사례
    if(idx == word.size()-1) return 1;
    // 메모이제이션
    int& ret = cache[y][x][idx];
    if(ret != -1) return ret;
    // 재귀 호출
    ret = 0;
    for(int i = 0; i < 4; i++){
        int ny = y;
        int nx = x;
        for(int j = 0; j < k; j++){
            ny += dy[i];
            nx += dx[i];
            if(0 <= ny && ny < n && 0 <= nx && nx < m){
                if(plate[ny][nx] == word[idx+1]){
                    ret += solve(ny, nx, idx+1);
                }
            }
        }
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m >> k;
    plate.resize(n);
    for(auto& i : plate) cin >> i;
    cin >> word;
    cache.resize(n, vector<vector<int>>(m, vector<int>(word.size(), -1)));
    int ans = 0;
    for(int y = 0; y < n; y++)
        for(int x = 0; x < m; x++)
            if(plate[y][x] == word[0])
                ans += solve(y, x, 0);
    cout << ans << "\n";
    return 0;
}

상하좌우 k 칸으로 이동할 수 있다는 문제의 조건이 이해가 가질 않아서 힘들었던 문제.

한번에 한칸씩 이동하며 여러칸을 이동할 수 있다는 의미가 아니라, 상하좌우로 k칸의 범위 내에서 한칸을 골라 이동할 수 있다는 의미였다.

문자판이 모두 같은 단어로 적혀져 있을때가 최악의 경우로 복잡도를 따로 계산해보지 않아도 시간초과가 날 것 같다. 현재 문자판의 좌표 그리고 일치한 문자열의 인덱스를 기준으로 문자열을 완성시킬 수 있는 경로의 개수를 메모이제이션하면 ac 를 받을 수 있다.