백준 2186번: 문자판 (C++)

접근

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

2186번: 문자판

처음에는 DFS 알고리즘을 이용하여 K칸 이동하는 식을 통해 문제를 해결하려 하였지만, 딱 봐도 시간초과일 것 같아 중복 계산을 막을 수 있는 방법을 찾기 시작하였다.

결과적으로는 DP[101][101][81]의 배열을 만들어 DP를 이용하여 풀 수 있었다. DP[a][b][c] = d 라고 할 때 이 의미는 MAP[a][b]에 있는 문자가 c번째로 쓰일 때, 가능한 정답의 갯수가 d개라는 의미이다. 이 수를 저장함으로써 중복 계산을 생략해줄 수 있다. 예를 들어, ABCDE라는 문자열을 찾을 때, 가능한 A가 2개이고 여기서 연결되는 B가 하나라면, 첫번째 A에서부터 탐색할 때 B에서 가능한 CDE의 개수를 이미 모두 탐색했으므로, 두번째 A에서 B로 왔을 때는 계산을 생략해도 될 것이다.

코드

#include <cstring>
#include <iostream>
#include <string>

using namespace std;

#define endl '\n'
#define MAX_N 101

int N, M, K;
char MAP[MAX_N][MAX_N];
int DP[MAX_N][MAX_N][81];
string word;
int word_len;

int dr[] = {0, 1, 0, -1};
int dc[] = {1, 0, -1, 0};

int dfs(int r, int c, int idx) {
    // 이미 탐색이 완료된 문자라면 리턴
    if (DP[r][c][idx] != -1) return DP[r][c][idx];
    // 단어의 마지막 알파벳의 DP 값은 1
    if (word_len <= idx) return 1;
    DP[r][c][idx] = 0;
    for (int i = 0; i < 4; i++) {
        for (int j = 1; j <= K; j++) {
            int nr = r + dr[i] * j;
            int nc = c + dc[i] * j;
            if (nr < 0 || N <= nr || nc < 0 || M <= nc) continue;
            if (MAP[nr][nc] != word[idx]) continue;
            DP[r][c][idx] += dfs(nr, nc, idx + 1);
        }
    }
    return DP[r][c][idx];
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    cin >> N >> M >> K;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> MAP[i][j];
        }
    }
    cin >> word;
    word_len = word.length();
    memset(DP, -1, sizeof(DP));

    int ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (MAP[i][j] == word[0]) {
                ans += dfs(i, j, 1);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!