[백준] 20166 문자열 지옥에 빠진 호석

문자열 지옥에 빠진 호석

---

주어진 이차원 배열을 8 방향으로 이동하며 가능한 모든 문자의 수를 구하고, 신이 좋아하는 단어가 나타나는 개수를 구하는 문제입니다. 문제의 조건은 아래와 같습니다.

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

일단 환형으로 이어지는 것에 유의해야합니다. 배열의 끝에 도달하더라도 세상은 환형으로 이어지기 때문에 다시 처음으로 돌아갑니다. 따라서 아래와 같이 이동 가능합니다.

D = ((-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1))

 for i in range(8):
    nr, nc = (row + D[i][0] + N) % N, (col + D[i][1] + M) % M

다음으로 이미 지나간 칸을 다시 지나가는 것을 허용 합니다. 따라서 가능한 문자를 구할 때 visited를 확인하는 연산은 하지 않습니다.

그리고 방문 순서가 다르면 다른 경우입니다. 따라서 순서가 존재하는 멱집합을 구해야합니다. 단, 신이 좋아하는 단어의 최대 길이는 5인 것에 유의해야합니다.

조건은 모두 살펴보았고, 이제 문자열을 어떻게 탐색할 지 정해야합니다. 다양한 방법이 있겠지만 문자열을 효율적으로 탐색할 수 있는 자료구조인 Trie를 사용합니다. Trie를 활용한 가능한 모든 문자를 만드는 알고리즘은 아래와 같습니다.

public static void permutate(int row, int col, StringBuilder current, int depth) {
    if (depth == 5)
        return;

    for (int i=0;i<8;i++) {
        int nr = (row + D[i][0] + N) % N;
        int nc = (col + D[i][1] + M) % M;

        current.append(board[nr][nc]); // 1
        trie.insert(current.toString()); // 2
        permutate(nr, nc, current, depth + 1); // 3
        current.setLength(current.length() - 1); // 4
    }
}

1. 현재 문자열에서 새로운 단어를 추가합니다
2. 만들어진 새로운 문자열을 Trie에 삽입합니다
3. 재귀적으로 반복합니다
4. 다음 경우를 위해 새로운 단어를 제거 합니다.

Java

import java.io.*;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class BOJ20166 {
    static class TrieNode {
        long count;
        Map<Character, TrieNode> children;

        TrieNode() {
            this.count = 0;
            this.children = new HashMap<>();
        }
    }

    static class Trie {
        TrieNode root;
        Trie() {
            root = new TrieNode();
        }

        public void insert(String word) {
            TrieNode node = this.root;

            for (char ch : word.toCharArray()) {
                node.children.putIfAbsent(ch, new TrieNode());
                node = node.children.get(ch);
            }
            node.count++;
        }

        public long search(String word) {
            TrieNode node = this.root;

            for (char ch : word.toCharArray()) {
                if (node.children.get(ch) == null) {
                    return 0;
                }
                node = node.children.get(ch);
            }

            return node.count;
        }
    }

    static Trie trie;
    static int N, M, K;
    static char[][] board;
    static String[] godWords;
    static int[] godWordsCount;
    static int[][] D = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
    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());

        trie = new Trie();

        board = new char[N][M];
        godWords = new String[K];
        godWordsCount = new int[K];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                board[i][j] = line.charAt(j);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                sb.append(board[i][j]);
                trie.insert(sb.toString());
                permutate(i, j, sb, 1);
                sb.setLength(0);
            }
        }

        for (int i = 0; i < K; i++) {
            godWords[i] = br.readLine();
            System.out.println(trie.search(godWords[i]));
        }
    }

    public static void permutate(int row, int col, StringBuilder current, int depth) {
        if (depth == 5)
            return;

        for (int i=0;i<8;i++) {
            int nr = (row + D[i][0] + N) % N;
            int nc = (col + D[i][1] + M) % M;

            current.append(board[nr][nc]);
            trie.insert(current.toString());
            permutate(nr, nc, current, depth + 1);
            current.setLength(current.length() - 1);
        }
    }
}

Python

from sys import stdin
from collections import defaultdict
readline = stdin.readline

class TrieNode:
    def __init__(self):
        self.count = 0
        self.children = defaultdict(TrieNode)

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root

        for char in word:
            node = node.children[char]

        node.count += 1

    def search(self, word):
        node = self.root

        for char in word:
            if char not in node.children:
                return 0

            node = node.children[char]

        return node.count


N, M, K = map(int, readline().split())
board = [list(readline()) for _ in range(N)]
god_words = [readline().strip() for _ in range(K)]
D = ((-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1))
trie = Trie()

def solve():
    for r in range(N):
        for c in range(M):
            trie.insert(board[r][c])
            permutate(r, c, board[r][c], 1)

    for i in range(K):
        print(trie.search(god_words[i]))

def permutate(row, col, current, depth):
    if depth == 5:
        return

    for i in range(8):
        nr, nc = (row + D[i][0] + N) % N, (col + D[i][1] + M) % M
        trie.insert(current + board[nr][nc])
        permutate(nr, nc, current + board[nr][nc], depth + 1)


solve()