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

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

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

#풀이

각 좌표에서 8가지 방향으로 이동할 수 있으며, 좌표가 범위를 넘어가지 않도록 구현해야 한다.

 

dfs를 이용하여 좌표에서 방향을 이동하여 문자열을 만들고 그 map을 통해 그 문자열의 경우의 수를 저장한다.

 

재귀를 통해서 dfs함수를 호출 할 때 마다 문자들을 더해서 문자열을 만들게 하였다.

 

신이 주는 문자열은 사이즈가 5개이므로 문자열의 사이즈가 5가 되면 함수를 종료하도록 하고

함수를 호출 할 때마다 문자열을 map에 저장하도록 했다.

 

신이 주는 문자열을 입력받으면서 재귀함수를 사용했는데 호출이 너무 많아서 시간초과가 났다.

 

그래서 먼저 1~5개의 문자열에 대한 경우의 수를 계산하고 문자열에 대한 경우의 수를 출력하게 했다.

 

#코드

#include<iostream>
#include<unordered_map>
#include<string>
using namespace std;
int n, m, k;
char arr[11][11];
int dx[8] = {0, 0, 1, 1, 1, -1, -1, -1  };
int dy[8] = {1, -1, 0, 1, -1, -1, 0, 1 };
unordered_map<string, int> map_;
void dfs(int x, int y, string s) {
	map_[s]++;
	if (s.size() == 5) { 
	
		return;
	}
	for (int i = 0; i < 8; i++) {
		int x2 = dx[i] + x;
		int y2 = dy[i] + y;
		if (x2 == 0) {
			x2 = n;
		}
		if (x2 == n+1) {
			x2 = 1;
		}
		if (y2 == 0) {
			y2 = m;
		}
		if (y2 == m+1) {
			y2 = 1;
		}

		dfs(x2, y2, s + arr[x2][y2]);
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> k;
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
		}
	}
	string str = "";
	for (int j = 1; j <= n; j++) {
		for (int k = 1; k <= m; k++) {
			dfs(j, k,str+ arr[j][k]);
		}
	}
	for (int i = 0; i < k; i++) {
		string str;
		cin >> str;
		cout << map_[str] << '\n';
	}
	
	return 0;
}