문제
NXM 격자에서, 왼쪽 위는 (1, 1), 오른쪽 아래는 (N, M)이다.
아무 곳에서 시작해서 상하좌우나 대각선 방향으로 한 칸씩 이동할 수 있으며, 이미 지나간 칸을 다시 방문해도 된다.
어떤 칸에서 시작해 이동할 때마다 그 칸에 써진 알파벳을 이어 붙여 문자열을 만들 수 있다.
문자열 K개가 주어지며, 각 문자열에 대해 만들 수 있는 경우의 수를 구하라.
방문 순서가 다르면 다른 경우로 센다. 예를 들어, (1,1)→(1,2)와 (1,2)→(1,1)은 서로 다른 경우다.
격자는 다음 규칙을 따른다:
1. 1행에서 위로 가면 N행으로, N행에서 아래로 가면 1행으로 간다.
2. 1열에서 왼쪽으로 가면 M열로, M열에서 오른쪽으로 가면 1열로 간다.
3. 대각선 방향도 동일하게 적용된다.
격자 정보와 K개의 문자열이 주어질 때, 각 문자열을 만들 수 있는 경우의 수를 구하라.
[풀이 코드]
import java.util.*;
import java.io.*;
public class Main {
static int N, M, K, result;
static char[][] arr;
public static void main(String[] args) throws Exception {
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());
arr = new char[N][M];
for (int i = 0; i < N; i++) {
String s = br.readLine();
for (int j = 0; j < M; j++) {
arr[i][j] = s.charAt(j);
}
}
for (int k = 0; k < K; k++) {
String target = br.readLine();
result = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if(arr[i][j] == target.charAt(0)) {
dfs(i, j, "", target);
}
}
}
System.out.println(result);
}
}
static int[] dr = {0, 0, 1, -1, 1, 1, -1, -1};
static int[] dc = {1, -1, 0, 0, 1, -1, 1, -1};
private static void dfs(int r, int c, String cur, String target) {
cur+=arr[r][c];
if(cur.equals(target)) {
result++;
return;
}
// 길이 초과되면 return
if(cur.length() > target.length()) return;
// 비교해서 맞지 않으면 return
if(!cur.equals(target.substring(0, cur.length()))) return;
for (int d = 0; d < 8; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if(nr==-1) nr=N-1;
if(nr==N) nr=0;
if(nc==-1) nc=M-1;
if(nc==M) nc=0;;
dfs(nr, nc, cur, target);
}
}
}위 코드는 내가 처음에 작성한 코드다.
예제에 나와있는 테스트 케이스를 입력했는데, 전부 답이 나와서 제출을 했지만 시간초과가 떳다.
그래서 가지치기를 더 해야하나 싶어서 생각을 해보았지만 떠오르지 않았고, 카페를 가기 위해 준비시간을 가지고 카페에 갔다.
카페에서 다른 작업을 한 후, 다시 이 문제를 풀려고 하는데, 도저히 생각이 나지 않아 지인한테 물어봤다. 지인은 가지치기를 했는데 시간초과가 나면 메모이제이션을 적용하면 금방 풀릴거라고 얘기했고, 아래와 같이 적용을 했다.
다음은 메모이제이션을 도입한 코드다.
import java.util.*;
import java.io.*;
public class Main {
static int N, M, K;
static char[][] arr;
static Map<String, Integer> dp;
static String target;
public static void main(String[] args) throws Exception {
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());
arr = new char[N][M];
for (int i = 0; i < N; i++) {
String s = br.readLine();
for (int j = 0; j < M; j++) {
arr[i][j] = s.charAt(j);
}
}
for (int k = 0; k < K; k++) {
target = br.readLine();
dp = new HashMap<>();
int result = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (arr[i][j] == target.charAt(0)) {
result += dfs(i, j, 0);
} }
}
// System.out.println(dp);
System.out.println(result);
}
}
static int[] dr = {0, 0, 1, -1, 1, 1, -1, -1};
static int[] dc = {1, -1, 0, 0, 1, -1, 1, -1};
private static int dfs(int r, int c, int depth) {
if (depth == target.length() - 1) return 1;
String key = r + "," + c + "," + depth;
if (dp.containsKey(key)) return dp.get(key);
int count = 0;
for (int d = 0; d < 8; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if(nr==-1) nr=N-1;
if(nr==N) nr=0;
if(nc==-1) nc=M-1;
if(nc==M) nc=0;;
if (arr[nr][nc] == target.charAt(depth+1)) {
count += dfs(nr, nc, depth+1);
}
}
dp.put(key, count);
return count;
}
}
Map을 사용해서, key에는 "r + c + 깊이"를 저장하고 value에는 그 상태에서 문자열을 완성할 수 있는 경우의 수다. 즉, 찾아야 하는 문자열이 "AB"라고 가정하면 arr[r][c] 가 "A" 인데 그 다음 문자로 "B"를 찾아야하는데, 그 경우의 수가 value이다.
이렇게 되면 이중 for문을 돌면서 각각 위치에서 문자열을 찾을 때, 이미 계산한 경로는 재활용이 되기때문에 불필요한 연산을 크게 줄일 수 있다.
