[백준] 2186-문자판(C++)

문제링크: https://www.acmicpc.net/problem/2186

2186번: 문자판

 

top-down방식의 dp를 사용해서 해결하는 문제였습니다.

 

문제 예시에서는 k가 1이라 break는 총 3가지 경우가 포함이 됩니다.

 

모든 그래프에 대해서 단순 dfs나 bfs로는 시간문제때문에 해결을 할 수 없습니다.

dp를 통해서 탐색했던 내용을 복사해두고 다음번 탐색에서 사용할 수 있도록 구현해야 합니다.

 

접근방식

 

1. 그래프 탐색을 통해서 문제를 해결하자.

 

2. 속도적인 문제 때문에 dp를 통해서 문제를 해결하자.

 

문제풀이 

 

1. dp[100][100][81]로 생성 좌표와 몇번째 단어인지를 나타내는 인덱스들이다.

 

2. k가 늘어남에 따라서 이동할 수 있는 칸이 늘어나는데, while문을 사용해서 이러한 문제를 해결했다.

 

아래는 정답 코드

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <cstring>
using namespace std;

int dp[100][100][81]; // 0 base
char arr[100][100];
string word;

int n, m, k;

int y_ar[4] = { -1,0,1,0 };
int x_ar[4] = { 0,1,0,-1 };

int result = 0;

int solved(int y, int x, int cnt) {

	
	if (cnt == word.size())
		return 1;

	int& ret = dp[y][x][cnt];
	if (ret != -1)
		return ret;

	ret = 0;

	for (int i = 0; i < 4; i++) {
		int  c = k;
		int ny = y;
		int nx = x;
		while (c--) {
			ny +=  y_ar[i];
			nx +=  x_ar[i];
			if (ny < 0 || ny >= n || nx < 0 || nx >= m)
				continue;
			if (arr[ny][nx] != word[cnt])
				continue;
			ret += solved(ny, nx, cnt + 1);
		}
	}

	return ret;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m >> k;

	for (int i = 0; i < n; i++)
		cin >> arr[i];

	cin >> word;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			for (int u = 0; u <= word.size(); u++)
				dp[i][j][u] = -1;



	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (arr[i][j] == word[0]) {
				result += solved(i, j, 1);
			}


	cout << result << endl;

	/*
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			cout << dp[i][j][1] << ' ';
		cout << endl;
	}*/

	return 0;
}