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

이번 문제는 백준의 골드 4 문제, 문자열 지옥에 빠진 호석 문제였다.
문제를 차근차근 한 번 읽어보도록 하자.

최대 10 x 10의 보드가 주어지고 보드에 문자가 적혀있다.
상하좌우 대각선으로 훑으며 문자열을 만들 수 있는 지 판단한다.

이 때 중요한 점은 보드가 환형으로 이어진다는 점이다.
벽을 넘어갔을 때, 반대편 보드의 지점으로 넘어갈 수 있다는 말이다.
또, 방문 순서가 다르면 다른 문자열 취급을 하도록 한다.
마지막으로 문자열은 중복되어 주어질 수 있다.

이 부분들을 주의하면 문제를 한 번 풀어보자.

DFS

문제를 딱 읽어보았을 때 드는 생각은 DFS였다.
물론 대각선까지 이동이 가능하기 때문에 8방향 DFS이다.
8방향으로 보드를 파고들며, 벽을 넘어가면 모듈러 연산을 해준다.
그럼 보드의 반대편 위치로 돌아오는 것이 구현 가능하다.

이 때 문제가 되는 부분은 음수가 되는 경우이다.
음수가 되는 경우에는 모듈러 연산이 제대로 동작하지 않는다.
따라서 음수의 경우에는 행 열의 크기만큼 더해주도록 하면 된다.

방문 순서가 다르면 다른 문자열 취급함은 어떻게 구현할까?
이 부분은 visit 배열로 방문 체크를 하지 않으면 될 것 같다.

문자열이 중복으로 주어지는 부분은, 해시 테이블을 이용할 것이다.
DFS를 돌며 구한 값을 해시 테이블에 저장하도록 한다.
그럼 추후에 같은 문자열이 들어왔을 때 DFS를 돌지 않아도 된다.

최종적으로 아래와 같이 구현하였다.

int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1};
void optimize() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

void dfs(int depth, int curr_x, int curr_y, string target, string curr_str) {
	// 8방향 dfs를 돌려보자
	if (depth == target.size()) {
		if (curr_str == target)
			hash_counter[target]++;

		return;
	}

	for (int i = 0; i < 8; i++) {
		int nx = (curr_x + dx[i]) % row;
		int ny = (curr_y + dy[i]) % col;

		if (nx < 0)
			nx += row;
		if (ny < 0)
			ny += col;

		string nx_str = curr_str + game_board[nx][ny];
		dfs(depth + 1, nx, ny, target, nx_str);
	}
}

string target_str = "";
int main() {
	optimize();
	cin >> row >> col >> num;
	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++)
			cin >> game_board[i][j];

	while (num--) {
		cin >> target_str;

		if (hash_counter[target_str])
			cout << hash_counter[target_str] << '\n';
		// 해시에 이미 값이 있으면 그대로 출력
		else {
			for (int i = 0; i < row; i++) {
				for (int j = 0; j < col; j++) {
					string init_str = "";
					init_str += game_board[i][j];

					dfs(1, i, j, target_str, init_str);
				}
			}

			cout << hash_counter[target_str] << '\n';
		}
		// 없으면 dfs 돌려서 검사
	}

	return 0;
}

하지만 이 코드는 시간초과를 받게 되었다.
어느 부분이 문제인지 좀 더 생각을 해보자.

문제 제대로 이해하기

찬찬히 코드를 다시 살펴보니, 굳이 로직이 저럴 필요가 없었다.
입력을 받을 때 마다 DFS를 돌아버려 시간초과가 난 것이다.

입력을 미리 다 받아놓고, DFS를 한 번만 돌리도록 로직을 바꾸자!
나오는 모든 문자열을 해시 테이블에 저장을 한 뒤에,
입력 받았던 문자열들을 차례차례 값만 뽑아내면 될 것 같다.

그렇게 방식을 바꾸기 위해서 DFS 로직도 변경했다.
중지 조건이 원래는 타겟 문자열이었다면,
최대 문자열 길이인 5가 되었을 때 중지하도록 했다.
그래야 모든 길이의 문자열이 해시에 저장되기 때문이다.

최종 구현은 아래와 같이 되었다.

int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1};
void optimize() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

void dfs(int depth, int curr_x, int curr_y, string curr_str) {
	// 8방향 dfs를 돌려보자
	if (depth > 5)
		return;

	hash_counter[curr_str]++;
	for (int i = 0; i < 8; i++) {
		int nx = (curr_x + dx[i]) % row;
		int ny = (curr_y + dy[i]) % col;

		if (nx < 0)
			nx += row;
		if (ny < 0)
			ny += col;

		string nx_str = curr_str + game_board[nx][ny];
		dfs(depth + 1, nx, ny, nx_str);
	}
}

int main() {
	optimize();
	cin >> row >> col >> num;
	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++)
			cin >> game_board[i][j];

	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			string init_str = "";
			init_str += game_board[i][j];

			dfs(1, i, j, init_str);
		}
	}

	for (int i = 0; i < num; i++) {
		cin >> target_str;
		cout << hash_counter[target_str] << '\n';
	}

	return 0;
}

코드도 훨씬 간결해지고, 시간도 많이 줄어들었다.