백준 20166 문자열 지옥에 빠진 호석

백준 20166

일반적인 bfs 문제와 달리 왔던 곳을 다시 방문할 수 도 있기 때문에 vis 배열은 안둬도 되고, 중복된 문자열이 올 수 있기 때문에 map 을 이용해서 처리해야한다. 그냥 bfs로 풀게되면 최악의 경우 1000 10^2 8^5으로 시간초과가 된다.

=> 일반적인 bfs 시간복잡도 = O(정점의 개수 x 간선의 개수)
=> 이 문제에서는 정점의 개수 10^2 , 간선의 개수 8^5 , 문자열의 개수 10^3

#include <bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;
int n, m, k;
int dx[8] = { -1,1,0,0,-1,-1,1,1 };
int dy[8] = { 0,0,-1,1,-1,1,-1,1 };
string s[1001];
vector<string> v;
map<string, int> mp;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	cin >> n >> m >> k;

	for (int i = 0; i < n; i++) cin >> s[i];
	
	for (int i = 0; i < k; i++) {
		string s;
		cin >> s;
		v.push_back(s);
	}

	queue<tuple<int, int, string, int>>q;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			
			string ss = "";
			ss += s[i][j];
			q.push({ i,j,ss,1 });

			while (!q.empty()) {

				int curX, curY, curCnt;
				string curS;

				tie(curX, curY, curS, curCnt) = q.front();
				q.pop();

				mp[curS]++;

				if (curCnt >= 5) continue;
				
				
				for (int i = 0; i < 8; i++) {

					int nx = (n + curX + dx[i]) %n; 
					int ny = (m+ curY + dy[i]) %m;

					q.push({ nx,ny,curS + s[nx][ny],curCnt+1 });
				}

			}
		}
	}
	
	for (int i = 0; i < v.size(); i++) {
		cout << mp[v[i]] << '\n';
	}

}