[ boj : 2418 ] 단어 격자

www.acmicpc.net/problem/2418

2418번: 단어 격자

문제 : 격자판이 주어지고 문자가 하나씩 써져있습니다. 이때 문자열이 주어지고 이 문자열을 만들 수 있는 경우의 수를 구하시오.

(문자의 중복방문이 허용됩니다)

 

해설 : 전형적인 DP문제입니다. 항상 '상태값'을 생각해봅니다. 먼저 가장 쉽게 생각할 수 있는 상태값 중 하나는 '좌표값'이 되겠죠. 내가 어느 좌표에 있는 지에 따라 답에 직접적으로 영향을 미치니까요. 그리고 또 생각해볼 수 있는 부분은 현재 좌표에 '언제' 왔느냐 입니다. 내가 현재 좌표에 3번째로 도달했는지 4번째로 도달했는지에 따라 답에 영향을 미칠 수 있기 때문이죠.

 

그럼 상태값의 개수를 알았으니 이를 '표현'해 줍시다.

 

DP[x][y][step] = (x,y)좌표에 step번째 도달했을때 만들 수 있는 경우의 수

 

참고로 배열의 초기값은 -1로 초기화 해주어야 합니다. 0인 경우의 수가 존재할 수도 있기 때문이죠.

 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int h, w, l;
ll dp[200][200][101];
string str[200],s;
int dx[] = { -1,1,0,0,-1,-1,1,1 }, dy[] = { 0,0,-1,1,-1,1,1,-1 };

ll dfs(int x, int y, int step);

int main()
{
	cin >> h >> w >> l;
	for (int i = 0; i < h; i++)
		cin >> str[i];
	cin >> s;
	memset(dp, -1, sizeof(dp));
	ll ans = 0;
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
			if (str[i][j] == s[0])
				ans+=dfs(i, j,0);
	cout << ans;
	return 0;
}
ll dfs(int x, int y,int step)
{
	ll& ret = dp[x][y][step];
	if (ret != -1)return ret;
	ret = 0;
	if (str[x][y] == s[l - 1] && step == l - 1)return ret = 1;

	for (int i = 0; i < 8; i++) {
		int tx = x + dx[i];
		int ty = y + dy[i];

		if (tx < 0 || tx >= h || ty < 0 || ty >= w)continue;

		if(str[tx][ty]==s[step+1])
			ret+=dfs(tx, ty, step + 1);
	}
	return ret;
}