> 문제
문제 : [문자판]
> 문제풀이
문자배열과 단어가 주어지면, 문자배열 임의 위치에서 시작하여 상하좌우 최대 K까지 이동하여 만들수 있는 단어의 갯수를 찾는 문제이다.
1<=M,N<=100, 1<=K<=5, 1<=단어길이<=80
배열 각각의 위치에서 시작하여 단어를 찾는데 완전탐색을 할 경우 시간이 터질것이다.
접근방법
- 피보나치 수열에서 메모이제이션을 쓰지 않고 Top-down 방식을 사용할 시, 중복된 결과값을 찾기위해 불필요한 연산을 하게된다. 이를 고려하면 각 배열에서 메모이제이션을 사용하여 풀이를 생각해볼 수 있다.
- 메모이제이션을 사용하기 위해서는 단어의 인덱스를 고려해야한다.
- 예를들어 AOAOAO 단어를 만들어야 하는 문자판이 있다면, 문자판에 A가 어느위치에 해당하는지 고려해줘야 한다.
- 3차원 배열을 사용하면 해결할 수 있다. 문자판 알파벳의 인덱스값에 메모이제이션을 적용하는 것이다.
소스는 다음과 같다.
package hd;
import java.io.*;
public class Main {
static int N,M,K;
static char[][] map;
static int[][][] dp;
static int[][] dir = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
static boolean check(int x, int y) {
if(x>=0 && x<N && y>=0 && y<M) return true;
else return false;
}
static int res;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().trim().split(" ");
N = Integer.parseInt(input[0]);
M = Integer.parseInt(input[1]);
K = Integer.parseInt(input[2]);
map = new char[N][M];
for(int i=0; i<N; i++) {
map[i] = br.readLine().trim().toCharArray();
}
char[] word = br.readLine().trim().toCharArray();
int length = word.length;
char start = word[0];
char end = word[length-1];
dp = new int[N][M][length];
int dx,dy;
for(int a=0; a<length-1; a++) {
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(map[i][j] == start) {
for(int d=0; d<4; d++) {
dx = i;
dy = j;
for(int k=0; k<K; k++) {
dx += dir[d][0];
dy += dir[d][1];
if(check(dx,dy) && map[dx][dy] == word[a+1]) {
dp[dx][dy][a+1] += (dp[i][j][a] == 0 && a==0) ? 1 : dp[i][j][a];
}
}
}
}
}
}
start = word[a+1];
}
int res = 0;
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(map[i][j] == end) {
res+=dp[i][j][length-1];
}
}
}
System.out.println(res);
}
}
문제 출처 : Programmers