C++ / 백준 / 2186 / 문자판

문제

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

2186번: 문자판

문제풀이

DFS로만 풀었는데 시간초과가 났다.

질문글+블로그를 보고 3차원 DP+DFS로 바꿔 풀었다.

DP[y][x][word_cnt]로 두고 같은 글자수 일때 이미 저장된 값이 있다면 DFS를 하지않고 DP의 값을 이용한다.

방문하지 않은 곳은 -1, 방문을 하면 0으로 바꾸고 DFS를 하여 값을 저장한다.

대충 DP는 이런 느낌이다.

3차원이라 DP에 저장된 숫자들은 없어지지 않고 남아있다.

BRB일 경우 B가 두번 있어 같은 위치를 두번 방문하게 되지만 DP[3][1][0], DP[3][1][2] 이므로 서로 값이 다르다.

BREAK의 처음 글자인 B가 하나밖에 없어 이 예제에선 크게 의미없다.

	for (y = 0; y < N; ++y)
		for (x = 0; x < M; ++x)
			if (board[y][x] == answer[0])
				ret += DFS(y, x, first, 0);

메인문의 코드다.

글자를 저장한 board에서 찾아야하는 첫글자가 같을때만 DFS를 하게 했고

DFS를 int 함수로 선언하여 return되는 값을 ret에 누적 저장한다.

int DFS(int y, int x, string word, int word_loc)

y는 y좌표, x는 x좌표, word는 현재 만든 단어, word가 answer랑 같을때까지 DFS를 반복한다.

마지막으로 word_loc는 answer단어가 배열로 따졌을때 몇번째 인덱스인지를 나타내는 변수이다.

int DFS(int y, int x, string word, int word_loc) {
	int idx = 0;
	int idx2 = 0;
	if (word == answer)	return 1;
	else if (DP[y][x][word_loc] != -1) return DP[y][x][word_loc];
	else {
		DP[y][x][word_loc] = 0;
		for (idx = 0; idx < 4; ++idx)
			for (idx2 = 1; idx2 <= K; ++idx2) {
				int n_y = y + idx2 * loc[idx][0];
				int n_x = x + idx2 * loc[idx][1];
				if (n_y >= 0 && n_y < N && n_x >= 0 && n_x < M) {
					if (answer[word_loc + 1] == board[n_y][n_x]) {
						DP[y][x][word_loc] += DFS(n_y, n_x, word + board[n_y][n_x], word_loc + 1);
					}
				}
			}
	}
	return DP[y][x][word_loc];
}

다음으로 갈 칸이 answer[word_loc+1]에 해당하는 글자이면 DFS함수를 실행한다.

word가 answer와 같다면 1을 return 해준다.

1부터 K칸 만큼 이동할수 있으므로 이중 for문으로 모든 경우의 수를 탐색한다.

 

 

 

코드

#include <iostream>
#include <vector>
using namespace std;
int N, M, K;
string answer;
vector<vector<char>>board;
vector<vector<vector<int>>>DP;
vector<vector<int>>loc = { {-1,0},{1,0},{0,-1},{0,1} };

int DFS(int y, int x, string word, int word_loc) {
	int idx = 0;
	int idx2 = 0;
	if (word == answer)	return 1;
	else if (DP[y][x][word_loc] != -1) return DP[y][x][word_loc];
	else {
		DP[y][x][word_loc] = 0;
		for (idx = 0; idx < 4; ++idx)
			for (idx2 = 1; idx2 <= K; ++idx2) {
				int n_y = y + idx2 * loc[idx][0];
				int n_x = x + idx2 * loc[idx][1];
				if (n_y >= 0 && n_y < N && n_x >= 0 && n_x < M) {
					if (answer[word_loc + 1] == board[n_y][n_x]) {
						DP[y][x][word_loc] += DFS(n_y, n_x, word + board[n_y][n_x], word_loc + 1);
					}
				}
			}
	}
	return DP[y][x][word_loc];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int y = 0, x = 0;
	cin >> N >> M >> K;
	board = vector<vector<char>>(N, vector<char>(M, ' '));
	DP = vector<vector<vector<int>>>(N, vector<vector<int>>(M, vector<int>(80, -1)));
	for (y = 0; y < N; ++y)
		for (x = 0; x < M; ++x)
			cin >> board[y][x];

	cin >> answer;
	string first = "";
	first = answer[0];
	int ret = 0;
	for (y = 0; y < N; ++y)
		for (x = 0; x < M; ++x)
			if (board[y][x] == answer[0])
				ret += DFS(y, x, first, 0);

	cout << ret;
}