백준 2186 - 문자판

1. 문제 정리
  - N * M 의 문자판에서 모든 칸은 대문자로 채워져있다.

  - 어떤 한 칸에서 시작했을 때, 이동 방향은 상하좌우 4방향이며 한번에 이동할 수 있는 칸은 1칸 이상, K칸 이하이다. 

  - 이동경로를 통해 만들 수 있는 문장의 수를 구한다.

  - 입력은 N M K가 한줄, 이후 N 줄은 칸에 채워질 대문자이며, 마지막 문장은 찾아야할 문장이다.
 
2. 접근
  - 처음에는 bfs로 접근하였으나, 방문했던 칸을 다시 방문할 수 있으며, 단순 bfs로 풀기에는 시간복잡도상 해결할 수 없었다.

  - dfs를 이용하여 중복된 칸을 허용할 수 있도록 하며, 시간 단축을 위해 메모이제이션을 함께 사용했다.
 
3. 풀이

#include<iostream>
#include<queue>
using namespace std;

int n, m, k;
char a[100][100];
int dp[100][100][80];
string comp = "";
int ans = 0;

struct pos{
    int x, y;
    int idx;
}typedef pos;

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

int dfs(pos p){
    if(dp[p.x][p.y][p.idx] != -1) return dp[p.x][p.y][p.idx];
    if(a[p.x][p.y] != comp[p.idx]) return 0;
    if(p.idx+1 == comp.length()) {
        return 1;
    }
    dp[p.x][p.y][p.idx] = 0;
    for(int i = 0; i < 4; i++){
        for(int j = 1; j <= k; j++){
            int nx = p.x + dx[i] * j;
            int ny = p.y + dy[i] * j;
            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            dp[p.x][p.y][p.idx] += dfs({nx, ny, p.idx+1});
        }
    }
    return dp[p.x][p.y][p.idx];
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> m >> k;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
        }
    }
    cin >> comp;

    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) for(int t = 0; t < 80; t++) dp[i][j][t] = -1;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            ans += dfs({i, j, 0});
        }
    }

    cout << ans;
}

  - int dp[100][100][80] : 메모이제이션을 위한 배열이다. 80인 이유는 문장의 최대 길이가 80이기에 설정하였다.

  - struct pos : 좌표값(int x, y)과 찾아야하는 문장의 몇번째 문자까지 찾아갔는 지(int idx)를 한번에 이용할 수 있게 만든 구조체이다.

  - int dfs(pos p, int idx) : 문자판에서 p 지점부터 dfs를 수행한다. 문자판에서 현재 확인하는 좌표와 어떤 문자까지 봤는지를 확인하여(p.x, p.y, p.idx) 해당 값을 이미 방문한 적이 있다면(dp[p.x][p.y][p.idx] != -1) 방문했을 때의 값을 가져와 계산하며, 그렇지 않을 경우 dp 배열의 해당 인덱스 값을 0으로 초기화하여 계산한다.

  - int main() : dfs를 n*m 번 실행하여, 모든 문자판의 좌표에 대하여 실행한다. 그 후 반환값을 ans 변수에 더하여 for loop가 끝나면(모든 좌표에 대하여 dfs를 수행했다면), ans를 출력하고 반환한다.
 
4. 소감

  최근에 메모이제이션을 쓸 일이 없었어서 단순 dfs로 풀었다가 시간 초과로 애를 먹었다. 시간을 줄이기 위한 방법을 찾던 중 이전에 DP를 풀면서 공부했던 메모이제이션이 생각났고, dfs에 메모이제이션을 적용하여 시간을 줄이는 방식으로 문제에 접근하였다.

  bfs로 풀지 못할 문제는 아닌 거 같아 보이지만 bfs에서는 메모이제이션을 적용하기가 쉽지 않아보이기도 하였고 해당 문제에는 dfs를 활용하는게 더 적합한 문제 풀이 방식이라 생각하여 위처럼 문제를 풀었다.

  메모이제이션을 한동안 안 썼다고 이렇게 접근 방식을 떠올리는데 시간을 많이 쓴 것에 반성하고 이전에 했던 공부도 언제든 돌아가서 다시 공부를 열심히 해봐야겠다.