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

https://www.acmicpc.net/problem/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
• 신이 좋아하는 문자열은 중복될 수도 있다.

 

문제 풀이

---

백트래킹 문제.

N * M 배열에 격자에 적혀있는 문자들을 저장한다. 한 번 방문한 곳을 다시 방문할 수 있음에 주의하며 백트래킹하여 문자열의 개수를 찾는다.  상하좌우 및 대각선 이동이 가능하고, 환형으로 이어지므로 다음으로 이동할 좌표가 -1이면 x좌표의 경우 N-1 , y 좌표의 경우 M-1로 이동시킨다. 또한 이동할 좌표가 x좌표가 N이거나 y 좌표가 M이라면 각 좌표를 0으로 이동시킨다. 이렇게 결정된 다음 이동 칸이 신이 좋아하는 문자열의 다음 문자와 일치한다면 백트래킹 함수를 재귀적으로 호출한다.

백트래킹 함수가 신이 좋아하는 문자열의 길이만큼 재귀적으로 호출되었다면 여태까지 지난 위치들을 이어 신이 좋아하는 문자열을 만들 수 있는 것이다. 따라서 경우의 수를 저장하는 answer 카운트를 1 증가시킨다.

 

계속해서 신이 좋아하는 문자열이 같은 경우 이미 답을 구했으나 또 다시 값을 구하느라 시간초과가 발생한다. 따라서 map을 이용해 <신이 좋아하는 문자열, 만들 수 있는 경우의 수>를 <key, value>로 저장한다. 만약 map에 해당 key가 존재한다면 value를 출력해주면 되고, 존재하지 않는다면 백트래킹을 사용해 경우의 수를 구하고 map에 저장해준다.

 

아래는 코드.

#include <iostream>
#include <map>
#include <utility>
using namespace std;
char** arr;
int N, M, K;
string findString;
long long answer = 0;
int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };

void backTracking(int depth, int currentX, int currentY)
{
	if (depth == findString.length()-1)
	{
		answer++;
	}
	else
	{
		for (int i = 0; i < 8; i++)
		{
			int nextX = currentX + dx[i];
			int nextY = currentY + dy[i];
			if (nextX == -1)
			{
				nextX = N - 1;
			}
			if (nextX == N)
			{
				nextX = 0;
			}
			if (nextY == -1)
			{
				nextY = M - 1;
			}
			if (nextY == M)
			{
				nextY = 0;
			}
			if (arr[nextX][nextY] == findString.at(depth + 1))
			{
				backTracking(depth + 1, nextX, nextY);
			}
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	string str;
	cin >> N >> M>>K;
	arr = new char*[N];
	map<string, long long> m;
	map<string, long long>::iterator it;
	for (int i = 0; i < N; i++)
	{
		arr[i] = new char[M];
		cin >> str;
		for (int j = 0; j < M; j++)
		{
			arr[i][j] = str.at(j);
		}
	}
	for (int k = 0; k < K; k++)
	{
		answer = 0;
		cin >> findString;
		it = m.find(findString);
		if (it == m.end())
		{
			for (int i = 0; i < N; i++)
			{
				for (int j = 0; j < M; j++)
				{
					if (arr[i][j] == findString.at(0))
					{
						backTracking(0, i, j);
					}
				}
			}
			m.insert({ findString, answer });
			cout << answer << "\n";
		}
		else
		{
			cout << it->second << "\n";
		}
	}
	return 0;
}