[BOJ/Gold 5] 백준 20166 문자열 지옥에 빠진 호석(C++)

문제 링크

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

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

 

문제

하루 종일 내리는 비에 세상이 출렁이고 구름이 해를 먹어 밤인지 낮인지 모르는 어느 여름 날

잠 들기 싫어 버티던 호석이는 무거운 눈꺼풀에 패배했다. 정신을 차려보니 바닥에는 격자 모양의 타일이 가득한 세상이었고, 각 타일마다 알파벳 소문자가 하나씩 써있다더라. 두려움에 가득해 미친듯이 앞만 보고 달려 끝을 찾아 헤맸지만 이 세상은 끝이 없었고, 달리다 지쳐 바닥에 드러누우니 하늘에 이런 문구가 핏빛 구름으로 떠다니고 있었다.

• 이 세상은 N행 M열의 격자로 생겼으며, 각 칸에 알파벳이 써있고 환형으로 이어진다. 왼쪽 위를 (1, 1), 오른쪽 아래를 (N, M)이라고 하자.
• 너는 아무 곳에서나 시작해서 상하좌우나 대각선 방향의 칸으로 한 칸씩 이동할 수 있다. 이 때, 이미 지나 왔던 칸들을 다시 방문하는 것은 허용한다.
• 시작하는 격자의 알파벳을 시작으로, 이동할 때마다 각 칸에 써진 알파벳을 이어 붙여서 문자열을 만들 수 있다.
• 이 곳의 신인 내가 좋아하는 문자열을 K 개 알려줄 터이니, 각 문자열 마다 너가 만들 수 있는 경우의 수를 잘 대답해야 너의 세계로 돌아갈 것이다.
• 경우의 수를 셀 때, 방문 순서가 다르면 다른 경우이다. 즉, (1,1)->(1,2) 로 가는 것과 (1,2)->(1,1) 을 가는 것은 서로 다른 경우이다.

호석이는 하늘을 보고서 "환형이 무엇인지는 알려달라!" 며 소리를 지르니 핏빛 구름이 흩어졌다가 모이며 아래와 같은 말을 그렸다.

• 너가 1행에서 위로 가면 N 행으로 가게 되며 반대도 가능하다.
• 너가 1열에서 왼쪽으로 가면 M 열로 가게 되며 반대도 가능하다.
• 대각선 방향에 대해서도 동일한 규칙이 적용된다.
• 하늘에 아래와 같은 그림을 구름으로 그려줄 터이니 이해해 돕도록 하여라.
• 예를 들어서, 너가 (1, 1)에서 위로 가면 (N, 1)이고, 왼쪽으로 가면 (1, M)이며 왼쪽 위 대각선 방향으로 가면 (N, M)인 것이다.

세상을 이루는 격자의 정보와, K 개의 문자열이 주어졌을 때, 호석이가 대답해야 하는 정답을 구해주도록 하자.

입력

첫번째 줄에 격자의 크기 N, M과 신이 좋아하는 문자열의 개수 K 가 주어진다.

다음에 N개의 줄에 걸쳐서 M개의 알파벳 소문자가 공백없이 주어진다. 여기서의 첫 번째 줄은 1행의 정보이며, N 번째 줄은 N행의 정보이다.

이어서 K개의 줄에 걸쳐서 신이 좋아하는 문자열이 주어진다. 모두 알파벳 소문자로 이루어져 있다.

출력

K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다.

제한

• 3 ≤ N, M ≤ 10, N과 M은 자연수이다.
• 1 ≤ K ≤ 1,000, K는 자연수이다.
• 1 ≤ 신이 좋아하는 문자열의 길이 ≤ 5
• 신이 좋아하는 문자열은 중복될 수도 있다.

예제 입력 1

3 3 2
aaa
aba
aaa
aa
bb

예제 출력 1

56
0

예제 입력 2

3 4 3
abcb
bcaa
abac
aba
abc
cab

예제 출력 2

66
32
38

알고리즘 분류

• 자료 구조
• 그래프 탐색

풀이

각 지점에서 출발해서 DFS를 수행한다. DFS를 수행하면서 모으는 문자열이 신이 원하는 문자열이라면 map 자료구조를 이용해서 해당 문자열이 key라고 했을 때의 value를 1 증가시킨다.

DFS를 수행하면서, 모으는 문자열의 길이가 5를 넘어갔다면 DFS를 종료해준다.

마지막으로 신이 원하는 문자열들의 각각의 개수들을 출력해준다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <bitset>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 11
#define LL long long
#define INF 1e9

using namespace std;
int N, M, K;
char MAP[MAX][MAX];
unordered_map<string, int> UM;
vector<string> Answer;

void Input() {
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++) {
		string S;
		cin >> S;
		for (int j = 0; j < M; j++) {
			MAP[i][j] = S[j];
		}
	}
	while (K--) {
		string Like;
		cin >> Like;
		UM.insert(make_pair(Like, 0));
		Answer.push_back(Like);
	};
}

void DFS(int Y, int X, string S) {
	if (S.size() > 5) {
		return;
	}
	if (UM.find(S) != UM.end()) {
		UM[S]++;
	}
	int nextY, nextX;
	// 상
	nextY = Y - 1;
	if (nextY == -1) {
		nextY = N - 1;
	}
	nextX = X;
	DFS(nextY, nextX, S + MAP[nextY][nextX]);

	// 하
	nextY = Y + 1;
	if (nextY == N) {
		nextY = 0;
	}
	nextX = X;
	DFS(nextY, nextX, S + MAP[nextY][nextX]);
	
	// 좌
	nextY = Y;
	nextX = X - 1;
	if (nextX == -1) {
		nextX = M - 1;
	}
	DFS(nextY, nextX, S + MAP[nextY][nextX]);

	// 우
	nextY = Y;
	nextX = X + 1;
	if (nextX == M) {
		nextX = 0;
	}
	DFS(nextY, nextX, S + MAP[nextY][nextX]);

	// 북서
	nextY = Y - 1;
	if (nextY == -1) {
		nextY = N - 1;
	}
	nextX = X - 1;
	if (nextX == -1) {
		nextX = M - 1;
	}
	DFS(nextY, nextX, S + MAP[nextY][nextX]);

	// 동북
	nextY = Y - 1;
	if (nextY == -1) {
		nextY = N - 1;
	}
	nextX = X + 1;
	if (nextX == M) {
		nextX = 0;
	}
	DFS(nextY, nextX, S + MAP[nextY][nextX]);

	// 남서
	nextY = Y + 1;
	if (nextY == N) {
		nextY = 0;
	}
	nextX = X - 1;
	if (nextX == -1) {
		nextX = M - 1;
	}
	DFS(nextY, nextX, S + MAP[nextY][nextX]);

	// 동남
	nextY = Y + 1;
	if (nextY == N) {
		nextY = 0;
	}
	nextX = X + 1;
	if (nextX == M) {
		nextX = 0;
	}
	DFS(nextY, nextX, S + MAP[nextY][nextX]);
}

void Settings() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			string S = "";
			S += MAP[i][j];
			DFS(i, j, S);
		}
	}
}

void Find_Answer() {
	for (int i = 0; i < Answer.size(); i++) {
		cout << UM[Answer[i]] << "\n";
	}
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}