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

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

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

 

	#include<iostream>
	#include<vector>
	#include<string>
	#include<unordered_map>
	using namespace std;
	char grid[11][11];
	unordered_map<string, int> m;
	int dx[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
	int dy[8] = { 1, 1, 1, 0, 0, -1, -1, -1 };
	int N, M, K;
	void dfs(int x, int y, string cur) {
	if (cur.length() > 5) return;
	m[cur]++;
	for (int i = 0; i < 8; i++) {
	int nx = x + dx[i];
	int ny = y + dy[i];
	if (nx >= N) nx = 0;
	else if (nx < 0) nx = N - 1;
	if (ny >= M) ny = 0;
	else if (ny < 0) ny = M - 1;
	dfs(nx, ny, cur + grid[nx][ny]);
	}
	}
	int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	string s;
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
	cin >> grid[i][j];
	}
	}
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
	s = grid[i][j];
	dfs(i, j, s);
	}
	}
	for (int i = 0; i < K; i++) {
	cin >> s;
	cout << m[s] << '\n';
	}
	return 0;
	}

view raw 20166.cpp hosted with ❤ by GitHub

dfs+해시

아무곳에서나 시작할 수 있고, 방문순서가 다르면 다른 것이며, 이미 방문했던 곳도 다시 방문할 수 있으므로 방문배열을 사용하지 않고 각 위치에서 시작하는 dfs를 적용해준다.

환형탐색이므로 범위를 넘어서면 초기화해주는 작업이 필요하다.