백준 13502 - 단어퍼즐 2 (C++)

문제

• 문제 링크

  
   BOJ 13502 - 단어퍼즐 2 
  

• 문제 요약

$5*5$의 맵과 미리 기록된 dict가 주어진다.
dict에 속한 단어 중 맵에서 8방 탐색을 통해 찾을 수 있는 단어의 수를 구해보자.

• 제한

TL : $2$ sec, ML : $128$ MB

알고리즘 분류

• 자료 구조(data structures)
• 문자열(string)
• 트리(trees)
• 트라이(trie)
• 그래프 이론(graphs)
• 그래프 탐색(graph_traversal)
• 깊이 우선 탐색(dfs)
• 백트래킹(backtracking)
• 런타임 전의 전처리(precomputation)

풀이

   문제 자체는 어렵지 않다. dict에 속한 단어들을 트라이에 다 때려 박은 다음 맵에서 백트래킹으로 찾아지는 단어의 수를 구해주면 된다.

처음에 dict를 string 배열에 다 때려박고 이를 순회하며 트라이에 추가하는 식으로 작성하였다.
그런데 virtual ML을 얻어 맞고 현실 부정을 하다가 바보짓 한 걸 깨달았다.
굳이 string 배열에 할당할 필요 없이, range based for 을 이용해 dict를 순회만 해주면 되니 말이다. (코드의 36행)

그렇게 전처리 후 탐색 하는 부분은 그냥 모든 지점에서 시작해보며 조사해주면 된다.
중복 제거를 위해 set 자료구조를 이용하였고 최종 set.size()가 찾을 수 있는 단어의 수가 되겠다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
int dy[]{ -1, 1, 0, 0, -1, -1, 1, 1 }, dx[]{ 0, 0, -1, 1, -1, 1, -1, 1 };
unordered_set <string> an;
char M[6][6], V[6][6];
struct T
{
    map <char, T*> p;
    int u{};
    void push(string& s, int i)
    {
        if (i == (int)s.size()) u = 1;
        else
        {
            if (!p.count(s[i])) p[s[i]] = new T();
            p[s[i]]->push(s, i + 1);
        }
    }
    int trav(string s, int _y, int _x)
    {
        int r{};
        if (u) r++, an.insert(s);
        for (int i{}; i < 8; i++)
        {
            int y(_y + dy[i]), x(_x + dx[i]);
            if (y && x && y < 6 && x < 6 && p.count(M[y][x]) && !V[y][x])
                V[y][x] = 1, p[M[y][x]]->trav(s + M[y][x], y, x), V[y][x] = 0;
        }
        return r;
    }
};
int main()
{
    T* R(new T()); string s{};
    for (string s : { })
        R->push(s, 0);
    for (int i(1); i < 6; i++)
        for (int j(1); j < 6; cin >> M[i][j++]);
    for (int i(1); i < 6; i++)
        for (int j(1); j < 6; j++)
            if (R->p.count(M[i][j]))
                V[i][j] = 1, R->p[M[i][j]]->trav(s + M[i][j], i, j), V[i][j] = 0;
    cout << an.size();
}

comment

코드 길이가 대충 26만 바이트인데, 이 문제의 길이 제한 버전에선 무려 65536B 제한이 걸린다.
다이아던데, 저건 뭐 어케 하는건지 감도 안오니 pass.