[ boj : 20166 ] 문자열 지옥에 빠진 호석

www.acmicpc.net/problem/20166

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

문제 : 호석이는 상하좌우, 대각선 방향으로 한칸씩 움직일 수 있습니다. 이때 격자의 범위를 벗어나도 다시 격자안으로 돌아올 수 있습니다. 이때 신이 만들고 싶어하는 문자열을 만들 수 있는 경우의 수를 구하시오

 

해설 : 문제 똑바로 안읽고 또 정말 간소한 차이로 엄청 해맸습니다 ㅠㅠㅠ(바보입니다 전)

먼저 제가 처음 생각했던 바는 대각선으로 격자 밖으로 넘어가면 그 대각선 방향 그대로로 다시 돌아올거라고 생각했었습니다.

이렇게 되는줄 알았어요;;;;;;;

근데 아니죠,,,,

• 너가 1행에서 위로 가면 N 행으로 가게 되며 반대도 가능하다.
• 너가 1열에서 왼쪽으로 가면 M 열로 가게 되며 반대도 가능하다.

이렇게 되죠....그리고 또 

• 신이 좋아하는 문자열은 중복될 수도 있다.

이게 뭔말인가 했어요.근데 입력되는 입력값이 중복된 값이 들어올 수도 있다는 뜻이었더라구요.

 

어쨌건 이를 유의한 채로 풀어봅시다.

먼저 단순히 dfs를 이용해서 커팅하는 식으로 하려고 하면 tle가 발생할 것입니다.

최악의 경우를 생각해 봅시다.

-신이 1000번의 입력이 주어지고 이 1000번 모두 문자열의 길이가 5이며 똑같은 문자열이 주어졌을때

-주어진 격자가 모두 한가지의 문자로만 이루어졌을때

이런 경우라면 O(1000 x 10 x 10 x 8^5) 정도가 되겠죠. 감당할 수가 없습니다.

 

따라서 다시 생각해보면, 먼저 그냥 나타나는 모든 경우의 수가 O(10x10x8^5) 이니 이를 전부 저장해 두고 난 후에 주어진 입력값에 맞는 정답을 내놓는 방식을 생각해 보면 됩니다.

 

자료구조 map을 이용해서 표현할 수가 있겠죠.

그럼 시간복잡도는 O(nm8^5) 이 되겠네요

#include<bits/stdc++.h>

using namespace std;

int n, m, k;
int ans;
string str[10];
map<string, int> mp;

int dx[] = { -1,1,0,0,-1,1,1,-1 }, dy[] = { 0,0,-1,1,1,1,-1,-1 };

void solve();
void dfs(int x, int y, int pos, string sum);

int main()
{
	string input = "";
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++)
		cin >> str[i];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			dfs(i, j, 0, input + str[i][j]);
	while (k--)
		solve();
	return 0;
}
void solve()
{
	string s;
	cin >> s;
	cout << mp[s] << "\n";
	ans = 0;
}
void dfs(int x, int y, int pos, string sum)
{	
	if (pos >= 5) {
		ans++;
		return;
	}
	mp[sum] += 1;
	for (int i = 0; i < 8; i++) {
		int tx = x + dx[i];
		int ty = y + dy[i];

		if (tx < 0)tx = n - 1;
		if (tx >= n)tx = 0;
		if (ty < 0)ty = m - 1;
		if (ty >= m)ty = 0;

		dfs(tx, ty, pos + 1, sum + str[tx][ty]);
	}
}