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

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

 

난이도 : 골드 4 
알고리즘 유형 : DP, DFS, 문자열 
풀이 시간 : 35분 

문제 풀이 

알파벳 소문자가 들어간 격자의 정보와 k개의 문자열이 주어졌을 때, 각 문자열마다 만들 수 있는 경우의 수를 출력하는 문제이다.

 

문제를 풀기에 앞서 제약 사항들이 주어진다.

 

- 상하좌우 대각선 방향으로 한 칸씩 이동하여 문자열을 이어붙일 수 있다.

- 이미 지나왔던 칸들을 다시 방문할 수 있다.

- 격자의 좌표를 벗어난 경우, 반대편으로 이동한다. (ex. (1, 1)에서 위로 이동하면 (n, 1))

- 중복된 문자열이 입력으로 주어질 수 있다.

 

해당 문제를 대략적으로 살펴봤을 땐, DFS 알고리즘을 사용해 가능한 경우의 수를 모두 찾아보는 방법이 있다. 하지만, 이미 지나왔던 칸들을 다시 방문할 수 있기 때문에 최악의 경우, $O(1000 * 10 * 10 * 8^5) = O(3276800000)$의 시간복잡도를 갖기 때문에 무조건 시간초과가 나게 될 것이다. 따라서, 이를 해결하기 위해 Top - Down DP 알고리즘을 활용하여 중복 방문을 피할 수 있다.

 

DP 테이블의 경우, 3차원으로 생성해주었다. (행 x 열 x 문자열 최대 길이)

이를 통해 문자열의 길이에 따른 중복 경우의 수를 방지해주어 매 문자열마다 DP 테이블을 초기화하지 않아도 된다.

 

또한, DFS에 재귀적으로 들어갈 때, 사전에 문자열의 문자가 맞는 경우에만 다음 재귀로 넘어가도록 조건을 추가해주어, 종료 조건에서 기존 문자열과 생성된 문자열이 같음을 보장해주었다.

 

마지막으로 문제에서 중요한 부분인, 중복 문자열이 입력으로 들어온 경우를 대비하기 위해서 `unordered_map` 라이브러리를 사용하였다. 
이를 통해 중복 문자열이 들어온 경우, 결과를 바로 출력해주어 시간을 단축시킬 수 있도록 하였다.

 

해당 코드의 시간복잡도는 최악의 경우, $O(1000 * 10 * 10 * (50 ~ 500))$로 계산할 수 있다.

 

코드

/*
헉 !

n행 m열, 각 칸에 알파벳 써있고 환형으로 이어짐
상하좌우 대각선 한 칸 이동 가능
	- 이미 지난 칸 다시 방문 가능
각 칸에 써진 알파벳을 이어붙여 문자열 만들기 가능
-문자열 k개 알려줄테니 너가 만들 수 있는 경우의 수를 잘 대답해야함
- 방문 순서가 다르면 다른 경우이다.

3 ≤ N, M ≤ 10
1 ≤ K ≤ 1,000
1 ≤ 문자열의 길이 ≤ 5
문자열 중복 가능 -> 해시로 값 저장해서 있는 값이면 출력

풀이 : depth는 총 5번 가능함 -> 깊지 않다. dfs 가능
모든 경우에 대해 살펴봐야 함 -> 시간초과임
	- 최적화 필요
경우의 수를 세는 경우니까 top-down dp 가능할지도 ?
	- 모든 경우에 대해 탑다운 적용하기 -> 1000 * 100 = 10만
*/

#include <iostream>
#include <string>
#include <cstring>
#include <unordered_map>

using namespace std;

int n, m, k, s_size;
char grid[11][11];
string s;

int dp[11][11][6]; // 최대 길이까지 저장
unordered_map<string, int> string_table;

int dr[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
int dc[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };

int top_down(int r, int c, int depth) {
	// 종료 조건 : 문자열이 맞는지는 사전에 검사했기 때문에 길이만 검사하면 된다.
	if (depth == s_size) 
		return 1;

	// DP 캐싱 확인
	if (dp[r][c][depth] != -1) 
		return dp[r][c][depth];

	dp[r][c][depth] = 0;

	// 8방향 탐색
	for (int d = 0; d < 8; d++) {
		int nr = (r + dr[d] + n) % n;
		int nc = (c + dc[d] + m) % m;
		if (grid[nr][nc] == s[depth]) {
			dp[r][c][depth] += top_down(nr, nc, depth + 1);
		}
	}
	return dp[r][c][depth];
}

void init() {
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) {
		cin >> s;
		for (int j = 0; j < m; j++)
			grid[i][j] = s[j];
	}
}

void solution() {
	while (k--) {
		cin >> s;

		// 이미 계산한 문자열이면 바로 출력
		if (string_table.count(s)) {
			cout << string_table[s] << '\n';
			continue;
		}

		s_size = s.size();
		memset(dp, -1, sizeof(dp));
		int answer = 0;

		// 모든 시작 위치 탐색
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (grid[i][j] == s[0]) {
					answer += top_down(i, j, 1);
				}
			}
		}

		cout << answer << '\n';
		string_table[s] = answer;
	}
}

int main() {
	init();

	solution();

	return 0;
}

배운 점 

경우의 수를 구하는 문제의 경우, 이제 탑다운 DP를 활용하여 무난하게 풀어낼 수 있다.

해당 문제의 경우, 문자열이 맞는지를 비교하는 문제였기 때문에 다음 결과가 이전 결과에 영향을 주지 않기 때문에 DP를 사용할 수 있었다.

하지만, 이전 결과와 다음 결과가 분리되어 있지 않으면 DP를 사용하지 못하기 때문에, 이는 문제를 풀면서 노하우로 쌓아가야 할 것 같다. 

 

행복한 설날 되세요 !!