2186 ๋ฌธ์žํŒ

์•Œ๊ณ ๋ฆฌ์ฆ˜(DFS, DP)

1. ๋ฌธ์žํŒ์„ ์ฃผ์–ด์ง„ ์กฐ๊ฑด๋Œ€๋กœ ์ˆœํšŒํ•˜๋˜, ๊ฒฐ๊ณผ๊ฐ’์ด int ์•ˆ์ด๋ผ๋Š” ๊ฑธ๋ณด๊ณ  ์—„์ฒญ ํด ์ˆ˜๋„ ์ž‡๋‹ค๋Š” ๊ฑธ ์˜ˆ์ธก or ๋น™๊ธ€๋น™๊ธ€ ๊ณ„์† ๋Œ ์ˆ˜ ์žˆ์œผ๋‹ˆ DP๊ฐ€ ์ž‡์–ด์•ผ๊ฒ ๋‹ค๊ณ  ์˜ˆ์ธก
2. DP๋ฅผ DP[r][c][d] ๋กœ ๊ตฌํ˜„ํ•˜๋˜, -1๋กœ ์ดˆ๊ธฐํ™”๋ฅผ ์‹œํ‚ค๊ณ , 0์ธ๊ฒƒ๋„ ๊ธฐ๋ก -> ๋ฌธ์ž์—ด์ด ์•„์˜ˆ ์—†์„ ์ˆ˜๋„ ์ž‡์œผ๋‹ˆ 0๋„ ๊ธฐ๋กํ•˜์—ฌ ๋” ๋นจ๋ฆฌ DP๊ฐ€ ๊ฐ€๋Šฅํ•ด์ง.

์ฝ”๋“œ

#include <bits/stdc++.h>
 
using namespace std;
 
int N, M, K, length, DP[101][101][81];
char board[101][101], keyword[81];
 
int generateDFS();
int DFS(int, int, int);
 
int main() {
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			cin >> board[i][j];
	string t;
	cin >> t;
	for (int i = 0; i < t.size(); i++)
		keyword[i] = t[i];
	length = t.size();
 
	cout << generateDFS();
}
 
int generateDFS() {
	int result = 0;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (board[i][j] == keyword[0])
				result += DFS(i, j, 0);
	return result;
}
 
int DFS(int r, int c, int d) {
	if (d == length - 1)
		return 1;
	if (DP[r][c][d] != 0)
		return DP[r][c][d];
 
	int result = 0;
	for (int i = 1; i <= K; i++) {
		if (r - i >= 0 && board[r - i][c] == keyword[d + 1])
			result += DFS(r - i, c, d + 1);
		if (r + i <= N - 1 && board[r + i][c] == keyword[d + 1])
			result += DFS(r + i, c, d + 1);
		if (c - i >= 0 && board[r][c - i] == keyword[d + 1])
			result += DFS(r, c - i, d + 1);
		if (c + i <= M - 1 && board[r][c + i] == keyword[d + 1])
			result += DFS(r, c + i, d + 1);
	}
	return DP[r][c][d] = result;
}