백준-2186 문자판

---

문제

---

실수한 부분

우선 문제를 딱 봤을 때, BFS를 생각했었다. 하지만, 가는 길에서 방문했던 곳을 다시 갈 수 있다는 곳에 혼란이 왔고, BFS로 하면 시간초과가 나올 거 같아 고민을 했던 문제다.
결국 문제를 검색해 풀이 방법을 보고 dp와 dfs로 푸는 방법을 대강 보고, 혼자서 구현해봤다.
그리고 예제를 통과하는 걸 보고, 제출 했다가 틀렸다… 이유는 자주 실수 하던 Valid 함수(boolean 함수)의 default 반환값을 설정안해서 틀렸다…
다음부터 주의하자.

구현

시간초과를 일으킬 중복 방문 문제는 dp로 해결했다. 전혀 방문하지 않은 상태는 -1로 설정하고, 방문한 뒤 dfs로 재귀 방식으로 가는 길의 경우의 수를 구했다.

#include <bits/stdc++.h>

using namespace std;

int N, M, K;
string Word;
vector<vector<char>> Board;
vector<vector<vector<int>>> DP;
int answer = 0;
int delPoint[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };

void init() {
	ios::sync_with_stdio(false);
	cin.tie(); cout.tie();
}

bool isValid(int row, int col) {
	if (N <= row || row < 0 || M <= col || col < 0)
		return false;
	return true;
}

int dfs(int row, int col, int idx) {
	if (Word.length()-1 <= idx)
		return 1;
	if (DP[row][col][idx] != -1)
		return DP[row][col][idx];
	DP[row][col][idx] = 0;

	for (int i = 0; i < 4; i++) {
		for (int j = 1; j <= K; j++) {
			int nRow = row + (delPoint[i][0] * j);
			int nCol = col + (delPoint[i][1] * j);

			if (!isValid(nRow, nCol))
				break;
			if(Board[nRow][nCol] == Word[idx + 1])
				DP[row][col][idx] += dfs(nRow, nCol, idx + 1);
		}
	}
	return DP[row][col][idx];
}

int main() {
	init();
	cin >> N >> M >> K;

	Board.resize(N,vector<char>(M));

	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < M; j++) {
			Board[i][j] = str[j];
		}
	}
	cin >> Word;
	DP.resize(N, vector<vector<int>>(M, vector<int>(Word.length(),-1)));
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (Word[0] == Board[i][j])
				answer += dfs(i, j, 0);
		}
	}
	cout << answer;
}