[ boj : 2168] 문자판

www.acmicpc.net/problem/2186

2186번: 문자판

문제 : 문자가 적혀있는 판이 주어지고 이동할 수 있는 k 값이 주어집니다. 이때 주어진 문자열을 만들수 있는 경우의 수를 구해라!

 

해설 : 정말 너무너무 싫고 어려운 다이나믹 프로그래밍 문제입니다. 전 dp 정말 몬해용,,,,ㅠㅠ

 

일단 정말 간단하게 생각해서 단순히 dfs,bfs 를 사용해서 하나씩 탐색해서 구할 수도 있겠죠.

그러나, 문제는 항상 '중복'입니다.

 

ex)

AAAAAAAAAAAAAAAAAAAAAA.............................

AAAAAAAAAAAAAAAAAAAAAA.............................

.

.

.

.

이렇게 100x100칸에 모든 문자가 A로 채워지고 구하려는 문자열이 AAAAAA................B 이런 케이스를 생각해보시면 모든 경우의 수를 확인하기에는 말도 안되는 시간복잡도를 가지게 되겠죠.(최소 지수승)

 

그럼 이제 다시 생각해 보는겁니다. 중복을 해결할 수 있는 방법은 무엇이 있을까?

'메모이제이션'이라는 기법을 사용해보는거죠.

이미 방문한 곳을 재방문 하였을때 어떤 흔적을 남겨놓는다면 우린 그 흔적만 사용해서 답을 도출하게끔

 

필자는 dfs로 문자들을 탐색하였고, 만약 지나온 경로들이 주어진 문자열을 만들 수 있다면 경우의 수가 1개 늘어난 것이니 1을 return 시켜주었습니다. 만약 중간 경로중에 다른 경로로도 문자열을 만들 수 있다면 1+1 = 2 가 되는 것이죠.

 

4 4 1

KAKT

XEAS

ZRWU

ZBQP

BREAK

 

여기서 dp 배열은

1 2 1 -1

-1 3 1 -1

-1 3 -1 -1

-1 3 -1 -1

이렇게 되겠죠.

 

근데 왜 dp 배열을 -1로 초기화 하나요??

이 부분은 0 으로 초기화 했을때 0이라는 값이 유효한 값이 될 수도 있기 때문입니다. 저 위의 케이스를 생각해보세요.

 

#include<bits/stdc++.h>

using namespace std;

string s;
string board[100];
int n, m, k;
int ans;
int dp[100][100][85];
int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 };

void solve();
int dfs(int x, int y, int cnt);

int main()
{
	int t = 0;

	//while (t--)
		solve();
}
void solve()
{	
	cin >> n >> m >> k;
	memset(dp, -1, sizeof(dp));
	for (int i = 0; i < n; i++)
		cin >> board[i];
	cin >> s;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (board[i][j] == s[0])
				ans += dfs(i, j, 0);
	cout << ans;
}
int dfs(int x, int y, int cnt)
{
	int& ret = dp[x][y][cnt];
	if (ret!=-1)return ret;

	ret = 0;
	if ((cnt == s.size() - 1 && board[x][y] == s[cnt])) {
		ret = 1;
		return ret;
	}
	for (int j = 1; j <= k; j++) {
		for (int i = 0; i < 4; i++) {
			int tx = x + dx[i] * j;
			int ty = y + dy[i] * j;

			if (tx < 0 || tx >= n || ty < 0 || ty >= m)continue;

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