[C++] 백준 20166번 : 문자열 지옥에 빠진 호석

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

20166번: 문자열 지옥에 빠진 호석

 

1. K 문자열마다 dfs로 문자열 만들어진 총 횟수 return -> 시간초과

2. K 문자열 중 가장 긴 값으로 dfs 재귀 1번 돌려서 각 재귀단계에서 만들어진 문자열 map 저장 후 value return 

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <set>
#include <sstream>
#include <map>

using namespace std;


int N, M, K;
char arr[10][10];
string str[1000];

pair<int, int> dir[8] = {
	{-1,-1},{-1,0},{-1,1}
	,{0,-1},		{0,1}
	,{1,-1},{1,0}, {1,1}
};

map<string, int> m;

void dfs(int y, int x, int cnt, string cStr) {
	m[cStr]++;
	
	if (cnt == 0)
		return;

	for (int i = 0; i < 8; i++) {
		int ny = y + dir[i].first, nx = x + dir[i].second;

		if (ny < 0) ny = N - 1;
		if (ny >= N) ny = 0;
		if (nx < 0) nx = M - 1;
		if (nx >= M) nx = 0;

		dfs(ny, nx, cnt - 1, cStr+arr[ny][nx]);		
	}
}


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

	cin >> N >> M >> K;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> arr[i][j];
		}
	}

	int maxLen = 0;
	for (int i = 0; i < K; i++) {
		cin >> str[i];
		if (maxLen < str[i].length())
			maxLen = str[i].length();
	}

	for (int j = 0; j < N; j++) {
		for (int k = 0; k < M; k++) {
			string tmp = "";
			dfs(j, k, maxLen - 1, tmp+arr[j][k]);
		}
	}
		
	for (int i = 0; i < K; i++) {
		cout << m[str[i]] << "\n";
	}


	return 0;
}