문제
N×M 문자판에서 상하좌우로 1~K칸 이동하여 주어진 단어를 만들 수 있는 경로의 수를 구하는 문제다.
핵심 아이디어
먼저 DFS로 현재 글자에서 다음 글자가 있는 칸을 찾아가면 된다. 문제는 서로 다른 경로가 같은 칸, 같은 글자 순서에 도착할 수 있다는 점이다. 그 뒤의 탐색 결과는 매번 같으므로 한 번만 계산해 저장한다. 이것이 메모이제이션이다.
dp[d][x][y]는 (x, y)에 서 있고 단어의 d번째 글자까지 맞춘 상태에서, 남은 단어를 완성하는 경로 수를 뜻한다. 예를 들어 목표가 ABCA라면 dp[1][2][3]은 (2, 3)의 B까지 찾은 뒤 C, A를 이어 만드는 방법의 수다.
여기서는 일반적인 길 찾기와 달리 방문 배열을 두면 안 된다. 문제에서 같은 칸을 다시 지나는 것을 허용하기 때문이다. 대신 d가 매 호출마다 1씩 늘어나므로 재귀는 반드시 끝난다.
풀이
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int n, m, k;
char tiles[101][101];
int dp[81][101][101];
string str;
int dirX[4] = {1, 0, -1, 0};
int dirY[4] = {0, 1, 0, -1};
int dfs(int x, int y, int d) {
if (dp[d][x][y] != -1) return dp[d][x][y];
if (d + 1 == str.size()) return 1;
int ret = 0;
for (int i = 0; i < 4; i++) {
for (int j = 1; j <= k; j++) {
int nx = x + dirX[i] * j;
int ny = y + dirY[i] * j;
if (nx >= n || ny >= m || nx < 0 || ny < 0) continue;
if (tiles[nx][ny] != str[d + 1]) continue;
ret += dfs(nx, ny, d + 1);
}
}
dp[d][x][y] = ret;
return ret;
}
int main() {
cin >> n >> m >> k;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> tiles[i][j];
cin >> str;
memset(dp, -1, sizeof(dp));
int ret = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (tiles[i][j] == str[0]) {
ret += dfs(i, j, 0);
}
}
}
cout << ret << endl;
return 0;
}
주요 포인트
dp초기값을-1로 설정해 “아직 계산 안 함”과 “계산했지만 경로가 0개”를 구분한다.- 이동 거리가 1~K칸이므로 내부 루프에서
j = 1 ~ k까지 탐색한다. - 다음 칸의 문자가
str[d + 1]과 같을 때만 재귀 호출한다. 현재 위치와 단어 인덱스를 함께 상태로 잡아야 같은 위치라도 진행 단계가 다른 경우를 구분할 수 있다.
복잡도
- 시간: O(N × M × L × K) — L: 단어 길이, K: 최대 이동 거리
- 공간: O(L × N × M)
이 문제의 핵심은 방문 여부가 아니라 현재 칸과 단어의 몇 번째 글자인가를 하나의 상태로 묶는 것이다.
댓글