문제 정의

아래 예처럼 알파벳이 적힌 N×N 사이즈(2≤N≤18)의 그리드가 있다. 오른쪽 위에서 왼쪽 아래로, 오른쪽 또는 아래로만 이동할 때, 지난 알파벳들이 팰린드롬^[1]이 되는 경우의 수를 구하라.

ABCD
BXZX
CDXB
WCBA

아이디어

처음 생각한 방법은 unordered_set<string> 타입의 upperLeft와 underRight를 만들고, 오른쪽 위와 왼쪽 아래에서 한칸씩 진행하면서, 새롭게 만들어지는 문자열을 다른 쪽의 set와 비교하여 팰린드롬이 될 가능성이 있으면 set에 추가하고, 아니면 버리는 식으로 문자열을 만들고자 하였다. 그러나 해당 방법은 시간 초과 되었다. 추측하건데 BFS와 유사한 방법으로 한칸씩 진행할 때마다 unordered_set을 초기화하고, 새로 만들고 하는 과정이 오래걸리는 건 아닐까 생각하였다.

다음에는 단순하게 DFS로 우 상단과 좌 하단을 잇는 대각선 위 원소로 만들 수 있는 모든 문자열을 upperLeft에 저장하고, 대각선 아래 원소로 만들 수 있는 모든 문자열을 underRight에 저장한 후, upperLeft와 underRight에 일치하는 문자열이 몇 개 있는지 세는 방법을 사용하였다.

풀이

아래 코드에서 우선 grid로 입력을 받는다. 그 다음 solution 함수가 호출되어, dfsTwoSide 함수가 먼저 호출된다. dfsTwoSide함수에서는 upperLeft와 underRight에 각각 만들 수 있는 문자열을 저장하는데, DFS를 사용하여 stack의 크기가 N이 되면 지나온 알파벳을 담고 있는 letters로 문자열을 만들어 set에 저장한다. 이때 방문 횟수를 기록하기 위해 visited 배열을 사용하는데, 아래쪽 방향과 오른쪽 방향으로 각각 진행해야 하기에, visited 배열을 정수형으로 만들어 첫 방문이면 1을 저장, 두번째 방문에는 2를 저장하도록 하였다.

upperLeft와 underRight가 완성되면, 두 set을 비교하여 동일한 문자열이 존재하면 팰린드롬이 되는 경우로 answerList에 추가하였다.

코드

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <unordered_set>
#include <utility>
using namespace std;

int N;
string grid[18][18];
int visited[18][18];
unordered_set<string> upperLeft[18];
unordered_set<string> underRight[18];
unordered_set<string> answerList;

// vector<string>을 string으로 만든다.
string buildString(vector<string> letters)
{
    string built = "";
    for (int i = 0; i < letters.size(); i++)
        built += letters[i];
    return built;
}

void dfsTwoSide(int visited[18][18])
{
    // DFS로 대각선 위 원소들로 만들 수 있는 모든 단어를 upperLeft에 저장한다.
    stack<pair<int, int>> visitStack;
    visitStack.push(make_pair(0, 0));

    // 현재 지나온 알파벳을 letters 배열에 저장한다.
    vector<string> letters;
    letters.push_back(grid[0][0]);

    while (!visitStack.empty())
    {
        pair<int, int> now = visitStack.top();

        if (visitStack.size() == N) {
            // 대각선 원소에 도달시 지나온 알파벳들을 upperLeft에 저장한다.
            upperLeft[now.first].insert(buildString(letters));
            letters.erase(--letters.end());
            visitStack.pop();
            continue;
        }

        if (visited[now.first][now.second] == 0) {
            // 처음 방문하면 아래쪽으로 진행한다.
            visited[now.first][now.second] = 1;
            if (now.first + 1 < N) {
                letters.push_back(grid[now.first + 1][now.second]);
                visitStack.push(make_pair(now.first + 1, now.second));
            }
        }
        else if (visited[now.first][now.second] == 1) {
            // 두번째 방문이면 오른쪽으로 진행한다.
            visited[now.first][now.second] = 2;
            if (now.second + 1 < N) {
                letters.push_back(grid[now.first][now.second + 1]);
                visitStack.push(make_pair(now.first, now.second + 1));
            }
        }
        else {
            // 양 방향 모두 진행하였으면 다시 방문 스택을 pop한다.
            visited[now.first][now.second] = 0;
            letters.erase(--letters.end());
            visitStack.pop();
        }
    }

    // 대각선 아래로 만들 수 있는 모든 단어를 lowerRight에 저장하는 작업을 똑같이 진행한다.
    visitStack.push(make_pair(N - 1, N - 1));
    letters.push_back(grid[N - 1][N - 1]);

    while (!visitStack.empty())
    {
        pair<int, int> now = visitStack.top();

        if (visitStack.size() == N) {
            underRight[now.first].insert(buildString(letters));
            letters.erase(--letters.end());
            visitStack.pop();
            continue;
        }

        if (visited[now.first][now.second] == 0) {
            visited[now.first][now.second] = 1;
            if (0 <= now.first - 1) {
                letters.push_back(grid[now.first - 1][now.second]);
                visitStack.push(make_pair(now.first - 1, now.second));
            }
        }
        else if (visited[now.first][now.second] == 1) {
            visited[now.first][now.second] = 2;
            if (0 <= now.second - 1) {
                letters.push_back(grid[now.first][now.second - 1]);
                visitStack.push(make_pair(now.first, now.second - 1));
            }
        }
        else {
            visited[now.first][now.second] = 0;
            letters.erase(--letters.end());
            visitStack.pop();
        }
    }
}

int solution()
{
    // upperLeft와 underRight를 만든다.
    dfsTwoSide(visited);

    for (int i = 0; i < N; i++) {
        for (string s : upperLeft[i]) {
            // 두 unordered_set을 비교해 동일한 문자열이 존재하면 경우의 수로 추가한다.
            if (underRight[i].find(s) != underRight[i].end())
                answerList.insert(s);
        }
    }
    // 정답은 경우의 수이므로, size를 반환한다.
    return answerList.size();
}

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

    cin >> N;
    string input;
    getline(cin, input);
    for (int n = 0; n < N; n++) {
        getline(cin, input);
        for (int i = 0; i < N; i++)
            grid[n][i] = input[i];
    }

    cout << solution() << '\n';

    return 0;
}

결과