[ BOJ ][JAVA][20166] 문자열 지옥에 빠진 호석

www.acmicpc.net/problem/20166

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

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	527	185	131	34.204%

문제

하루 종일 내리는 비에 세상이 출렁이고 구름이 해를 먹어 밤인지 낮인지 모르는 어느 여름 날

잠 들기 싫어 버티던 호석이는 무거운 눈꺼풀에 패배했다. 정신을 차려보니 바닥에는 격자 모양의 타일이 가득한 세상이었고, 각 타일마다 알파벳 소문자가 하나씩 써있다더라. 두려움에 가득해 미친듯이 앞만 보고 달려 끝을 찾아 헤맸지만 이 세상은 끝이 없었고, 달리다 지쳐 바닥에 드러누우니 하늘에 이런 문구가 핏빛 구름으로 떠다니고 있었다.

• 이 세상은 N행 M열의 격자로 생겼으며, 각 칸에 알파벳이 써있고 환형으로 이어진다. 왼쪽 위를 (1, 1), 오른쪽 아래를 (N, M)이라고 하자.
• 너는 아무 곳에서나 시작해서 상하좌우나 대각선 방향의 칸으로 한 칸씩 이동할 수 있다. 이 때, 이미 지나 왔던 칸들을 다시 방문하는 것은 허용한다.
• 시작하는 격자의 알파벳을 시작으로, 이동할 때마다 각 칸에 써진 알파벳을 이어 붙여서 문자열을 만들 수 있다.
• 이 곳의 신인 내가 좋아하는 문자열을 K 개 알려줄 터이니, 각 문자열 마다 너가 만들 수 있는 경우의 수를 잘 대답해야 너의 세계로 돌아갈 것이다.
• 경우의 수를 셀 때, 방문 순서가 다르면 다른 경우이다. 즉, (1,1)->(1,2) 로 가는 것과 (1,2)->(1,1) 을 가는 것은 서로 다른 경우이다.

호석이는 하늘을 보고서 *"환형이 무엇인지는 알려달라!"* 며 소리를 지르니 핏빛 구름이 흩어졌다가 모이며 아래와 같은 말을 그렸다.

• 너가 1행에서 위로 가면 N 행으로 가게 되며 반대도 가능하다.
• 너가 1열에서 왼쪽으로 가면 M 열로 가게 되며 반대도 가능하다.
• 대각선 방향에 대해서도 동일한 규칙이 적용된다.
• 하늘에 아래와 같은 그림을 구름으로 그려줄 터이니 이해해 돕도록 하여라.
• 예를 들어서, 너가 (1, 1)에서 위로 가면 (N, 1)이고, 왼쪽으로 가면 (1, M)이며 왼쪽 위 대각선 방향으로 가면 (N, M)인 것이다.

세상을 이루는 격자의 정보와, K 개의 문자열이 주어졌을 때, 호석이가 대답해야 하는 정답을 구해주도록 하자.

입력

첫번째 줄에 격자의 크기 N, M과 신이 좋아하는 문자열의 개수 K 가 주어진다.

다음에 N개의 줄에 걸쳐서 M개의 알파벳 소문자가 공백없이 주어진다. 여기서의 첫 번째 줄은 1행의 정보이며, N 번째 줄은 N행의 정보이다.

이어서 K개의 줄에 걸쳐서 신이 좋아하는 문자열이 주어진다. 모두 알파벳 소문자로 이루어져 있다.

출력

K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다.

제한

• 3 ≤ N, M ≤ 10, N과 M은 자연수이다.
• 1 ≤ K ≤ 1,000, K는 자연수이다.
• 1 ≤ 신이 좋아하는 문자열의 길이 ≤ 5
• 신이 좋아하는 문자열은 중복될 수도 있다.

예제 입력 1

3 3 2
aaa
aba
aaa
aa
bb

예제 출력 1

56
0

예제 입력 2

3 4 3
abcb
bcaa
abac
aba
abc
cab

예제 출력 2

66
32
38

코드

import java.io.*;
import java.util.*;

public class p20166 {
    static int n, m, k;
    static char[][] map;
    static int[] dx = {-1, -1, -1, 0, 1, 1, 1, 0};
    static int[] dy = {-1, 0, 1, 1, 1, 0, -1, -1};
    static Trie trie;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken()); // 신이 좋아하는 문자열

        map = new char[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            String input = br.readLine();
            for (int j = 1; j <= m; j++) {
                map[i][j] = input.charAt(j - 1);
            }
        }
        trie = new Trie();
        StringBuilder sb = new StringBuilder();

        for (int i = 1; i <= n; i++) {
            for  (int j = 1; j <= m; j++) {
                sb.append(map[i][j]);
                trie.insert(sb.toString());
                makeTrie(i, j, sb, 1);
                sb.setLength(0);
            }
        }

        while (k-- > 0) {
            String god = br.readLine();
            sb.append(trie.find(god)).append("\n");
        }
        System.out.println(sb);
    }

    static class TrieNode {
        Map<Character, TrieNode> childNodes;
        int cnt;
        TrieNode() {
            childNodes = new HashMap<>();
            cnt = 0;
        }
    }

    static class Trie {
        TrieNode rootNode;
        Trie () {
            rootNode = new TrieNode();
        }
        void insert(String s) {
            TrieNode thisNode = this.rootNode;
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                thisNode = thisNode.childNodes.computeIfAbsent(c, key ->  new TrieNode());
            }
            thisNode.cnt = thisNode.cnt + 1;
        }

        int find(String s) {
            TrieNode thisNode = this.rootNode;
            for (int i = 0; i < s.length(); i++)  {
                char  c = s.charAt(i);
                if (!thisNode.childNodes.containsKey(c)) return 0;
                thisNode = thisNode.childNodes.get(c);
            }
            return thisNode.cnt;
        }
    }

    static void makeTrie(int x, int y, StringBuilder sb, int len) {
        if (len == 5) return;
        for (int i = 0; i < 8; i++) {
            int nx = (x + dx[i]) % n;
            int ny = (y + dy[i]) % m;
            if (nx <= 0) nx += n;
            if (ny <= 0) ny += m;

            sb.append(map[nx][ny]);
            trie.insert(sb.toString());
            makeTrie(nx, ny, sb, len + 1);
            sb.setLength(sb.length() - 1);
        }
    }
}