Mini
[틀림] 백준 문자열 지옥에 빠진 호석 // 문자열, 먼저계산 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();
}
}
'Algorithm > dp' 카테고리의 다른 글
[세모] 프로그래머스 완전범죄 // dp, void dfs dp (0) | 2025.05.13 |
---|---|
[틀림] 백준 20181 꿈틀꿈틀 호석 애벌레 // 투포인터 dp (0) | 2025.05.12 |
[맞음] 백준 2156 포도주시식 // dp (0) | 2025.04.29 |
[틀림] 백준 1480 보석모으기 // 가방여러개 dp (0) | 2025.04.24 |
[틀림 세모] 백준 14863 서울에서 경산까지 // dfs dp, ret초기값 주의 (0) | 2025.04.06 |