[틀림] 백준 문자열 지옥에 빠진 호석 // 문자열, 먼저계산 dp, dfs

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

* 시도1

10*10 이니까 그냥 dfs로 완탐하면 될듯? -> 시간초과

100칸마다 각각 8방향 && depth 5제한 

 

* 풀이

미리 계산후, 쿼리하는 방식으로 개선

시간복잡도 : 3,276,800(3백만) + 1000(조회)

정답코드

dfs가 과거풀이,

dfs2가 캐시 미리계산 코드.

string을 인자로 넘기는게 범인이 아니었음.

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

public class Main {

    static int ret, n, m, k;
    static char[][] arr = new char[14][14];
    static int[] dx = {0, 1, 0, -1, -1, 1, -1, 1};
    static int[] dy = {1, 0, -1, 0, -1, 1, 1, -1};
    static HashMap<String, Integer> cache = new HashMap<>();

    static void dfs(int y, int x, int depth, String s, String target) {
        if (s.length() == target.length()) {
            if (s.equals(target)) {
                ret++;
            }
            return;
        }

        for (int i = 0; i < 8; ++i) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0) {
                ny = n - 1;
            }
            if (nx < 0) {
                nx = m - 1;
            }
            if (ny >= n) {
                ny = 0;
            }
            if (nx >= m) {
                nx = 0;
            }
            dfs(ny, nx, depth + 1, s + arr[ny][nx], target);
        }
    }

    static void dfs2(int y, int x, int depth, String s) {
        if(s.length()==6){
            return;
        }
        if(cache.containsKey(s)){
            cache.put(s,cache.get(s)+1);
        }
        else{
            cache.put(s,1);
        }

        for (int i = 0; i < 8; ++i) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0) {
                ny = n - 1;
            }
            if (nx < 0) {
                nx = m - 1;
            }
            if (ny >= n) {
                ny = 0;
            }
            if (nx >= m) {
                nx = 0;
            }
            dfs2(ny, nx, depth + 1, s + arr[ny][nx]);
        }
    }

    public static void main(String[] args) throws IOException {
        // FastIO implementation
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        for (int i = 0; i < n; ++i) {
            String tmp = br.readLine();
            for (int j = 0; j < m; ++j) {
                arr[i][j] = tmp.charAt(j);
            }
        }

        //모든 경우 미리계산!
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                dfs2(i, j, 0, String.valueOf(arr[i][j]));
            }
        }

        for (int q = 0; q < k; ++q) {
            String target = br.readLine();
            sb.append(cache.getOrDefault(target,0)).append("\n");
        }

//        for (int q = 0; q < k; ++q) {
//            String target = br.readLine();
//            ret = 0;
//
//            if(cache.containsKey(target)){
//                ret = cache.get(target);
//            }
//            else{
//                for (int i = 0; i < n; ++i) {
//                    for (int j = 0; j < m; ++j) {
//                        dfs(i, j, 0, String.valueOf(arr[i][j]), target);
//                    }
//                }
//                cache.put(target, ret);
//            }
//            sb.append(ret).append("\n");
//        }

        System.out.println(sb);
        br.close();
    }
}