백준 2186번 문자판

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

2186번: 문자판

DFS + DP 문제였습니다.

처음에는 DFS 알고리즘만 적용했는데 시간초과가 발생했습니다.

(최대 100 * 100 보드판에 최대 80 길이의 문자열을 찾아야하고 visited 배열을 사용할 수 없기 때문에 당연히 TLE가 발생합니다.)

따라서, 각 칸과 목표 문자열의 인덱스를 기준으로 캐싱하여 DP를 적용하면 시간초과를 방지할 수 있습니다.

 

	#include <iostream>
	#include <string>
	#include <vector>
	#include <cstring>
	using namespace std;
	const int MAX = 100;
	const int MAX_LENGTH = 80;
	typedef struct
	{
	int y, x;
	}Dir;
	Dir moveDir[4] = { { 1, 0 },{ -1, 0 },{ 0, 1 },{ 0, -1 } };
	int N, M, K;
	int result;
	string target;
	string board[MAX];
	int cache[MAX][MAX][MAX_LENGTH];
	int func(int y, int x, int idx)
	{
	int &result = cache[y][x][idx];
	if (result != -1)
	{
	return result;
	}
	if (idx == target.length())
	{
	return 1;
	}
	result = 0;
	for (int k = 0; k < 4; k++)
	{
	int tempY = y;
	int tempX = x;
	for (int i = 0; i < K; i++)
	{
	int nextY = tempY + moveDir[k].y;
	int nextX = tempX + moveDir[k].x;
	if (nextY < 0 || nextY >= N || nextX < 0 || nextX > M)
	{
	break;
	}
	if (board[nextY][nextX] == target[idx])
	{
	result += func(nextY, nextX, idx + 1);
	}
	tempY = nextY;
	tempX = nextX;
	}
	}
	return result;
	}
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++)
	{
	cin >> board[i];
	}
	cin >> target;
	vector<pair<int, int>> start;
	for (int i = 0; i < N; i++)
	{
	for (int j = 0; j < M; j++)
	{
	if (board[i][j] == target[0])
	{
	start.push_back({ i, j });
	}
	}
	}
	memset(cache, -1, sizeof(cache));
	for (int i = 0; i < start.size(); i++)
	{
	int y = start[i].first;
	int x = start[i].second;
	result += func(y, x, 1);
	}
	cout << result << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~