20166. 문자열 지옥에 빠진 호석

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

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

 

풀이

필요 지식: 다이나믹 프로그래밍, 해시

 

타일을 이동하며 신이 좋아하는 문자열을 찾아야 하는데, 꼭 DFS를 써야 할 것만 같다. 그런데 이미 지나온 칸을 다시 방문할 수 있다는 점이 구현을 난감하게 한다. 문자열이 ababa 같은 거라면 a와 b가 써진 두 칸만 왔다갔다거려도 된다는 건데, 이는 방문 여부를 체크할 때 또다른 생각할 거리를 안겨준다.

 

필자는 DFS를 응용하는 것에 쥐약인지라 다른 방법으로 풀어보기로 했고, 그러다 다이나믹 프로그래밍을 활용하는 풀이를 알아냈다. 요점은 길이 1, 2, …, n의 문자열을 만들기 위해 이동하는 경우의 수를 저장하는 것이다.

 

먼저 N행 M열의 문자들을 저장하는 2차원 배열 grid, 3차원 배열 dp를 선언하자. dp[n][i][j]는 n번째 인덱스까지의 문자열이 있고, 마지막 문자가 grid[i][j]일 때, 이 문자열을 만들기 위해 이동하는 경우의 수이다.

DP 점화식을 구하기 위해 문제의 예제 2에서 문자열이 aba인 경우를 생각해 보자. 먼저 n = 0일 때, 문자열은 a이며, 이 문자열의 마지막 문자 역시 a이다. 이때 dp[0][i][j]의 값은 grid[i][j] = 'a'일 경우 1을 저장하며, 이것이 점화식의 초기값이 된다.

n = 1일 때 문자열은 ab이며, 마지막 문자는 b가 된다. 그러므로 grid[i][j] = 'b'를 만족하는 dp[1][i][j]에 값을 넣는데, 이때 dp[0]의 값을 참조하게 된다. dp[0]에는 이전 문자인 a까지의 문자열을 만들기 위해 이동하는 경우의 수가 저장되어 있으므로, b까지의 문자열을 만드는 경우의 수는 문자가 b인 칸을 중심으로 1칸 주변의 dp[0]의 값을 전부 더하면 된다. 물론, 문제에서 주어졌듯이 범위를 벗어나면 첫 칸이나 마지막 칸으로 이동하는 걸 고려하도록 한다.

n = 2일 때 문자열은 aba이며, 마지막 문자는 a이다. 마찬가지로 ab를 만들고자 이동하는 경우의 수가 저장된 dp[1]을 참조하여, dp[2]의 값을 채운다. grid[i][j] = 'a'인 칸을 중심으로 1칸 주변의 dp[1]의 값을 전부 더한다. 그리고 dp[2]의 값을 총합하면 aba를 만들고자 이동하는 경우의 수는 66이 되며, 이는 예제의 정답과 일치한다.

 

해당 알고리즘의 점화식을 요약하면 다음과 같다. 여기서 str은 경우의 수를 찾고자 하는 문자열이며, 편의상 i - 1, i + 1, j - 1, j + 1이 범위를 벗어날 경우는 무시하였다.

• dp[0][i][j] = 1; (if grid[i][j] = str[0])
• dp[n][i][j] = accumulate(&dp[n - 1][i - 1][j - 1], &dp[n - 1][i - 1][j - 1] + 3, 0)
+ accumulate(&dp[n - 1][i][j - 1], &dp[n - 1][i][j - 1] + 3, 0) - dp[n - 1][i][j]
+ accumulate(&dp[n - 1][i + 1][j - 1], &dp[n - 1][i + 1][j - 1] + 3, 0);
  (if grid[i][j] = str[n])

이렇게 주어지는 문자열마다 DP로 풀어나가면 되겠지만, 문제는 문자열이 최대 1000개로, 중복해서 주어질 수도 있다는 것이다. 만약 같은 문자열이 수십~수백 개 주어진다면 이미 구한 걸 또 구하는 셈이니 실행 시간을 상당히 낭비한다는 생각이 든다. 

 

이를 보완하기 위해 해시를 활용한 컨테이너 <unordered_set>을 이용할 것이다. 이미 구한 문자열의 경우의 수를 해시 자료구조에 저장하고, 그 문자열이 주어지면 해당하는 값을 즉시 꺼내 출력하면 된다. 해시 자료구조는 시간 복잡도가 \(O(1)\)이므로 속도도 매우 빠르다.

 

시간 복잡도

주어지는 문자열의 길이를 \(L\)이라 하면, DP의 시간 복잡도는 \(O(LMN)\)이다. 만약 \(K\)개의 문자열이 전부 중복일 경우 시간 복잡도는 \(O(LMN)\), 전부 다를 경우(worst case) 시간 복잡도는 \(O(KLMN)\)이다.

 

소스코드

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int N, M, K;
int dx[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int dy[] = {-1, -1, -1, 0, 0, 1, 1, 1};
char grid[11][11];
unordered_map<string, int> um;

// 점화식 구현
void count(int (&dp)[5][11][11], int n, int i, int j) {
    for(int a = 0; a < 8; a++) {
        int nx = i + dx[a], ny = j + dy[a];
        if(nx < 0) nx = N - 1;
        else if(nx >= N) nx = 0;
        if(ny < 0) ny = M - 1;
        else if(ny >= M) ny = 0;
        
        dp[n][i][j] += dp[n - 1][nx][ny];
    }
}

// 문자열을 만들 수 있는 경우의 수를 구하는 함수
int solve(string str) {
    int dp[5][11][11] = {0, };
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(grid[i][j] == str[0]) dp[0][i][j] = 1;
        }
    }
    
    int len = str.length();
    for(int n = 1; n < len; n++) {
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(grid[i][j] == str[n]) count(dp, n, i, j);
            }
        }
    }
    
    int result = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            result += dp[len - 1][i][j];
        }
    }
    
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N >> M >> K;
    for(int i = 0; i < N; i++) {
        cin >> grid[i];
    }
    
    while(K--) {
        string str;
        cin >> str;
        
        // 같은 문자열의 경우의 수는 1번만 계산
        if(um.find(str) == um.end()) {
            int num = solve(str);
            um.emplace(str, num);
        }
        
        cout << um[str] << '\n';
    }
    
    return 0;
}