2186 문자판

 

 

 

dp 와 dfs 를 이용한다.

 

거꾸로 찾아나가는 방식이다.

BREAK 이 문자를 찾아나가야 할 때,

 

dp[1][2][3] = 위치(1,2) 에서 시작된 문자로 

BREAK 문자열의 3번째 부터 끝 문자열까지 완성할 수 있는 경우의 수이다.

즉, AK 를 완성할 수 있는 경우의 수로,

 

KAKT
XEAS
YRWU
ZBQP

 

위치 (1,2) 의 문자열 = A인데,

여기에서 좌,우,위, 아래로 움직여서 K가 있는 경우를 찾아보면 한 가지 경우를 찾을 수 있다.

때문에 dp[1][2][3] = 1 이다.

 

 

 

(1) 코드 설명 

 

KAKT
XEAS
YRWU
ZBQP

 

1) 

BREAK에서 맨 처음 문자 B가 있는 위치(3,1)에서 dfs가 시작한다.

 

 

===============================

 

KAKT
XEAS
YRWU
ZBQP

 

2) 

(3,1)의 위치에서 좌,우,위,아래 방향으로 다음 글자인

R이 있는 위치 (2,1) 에서 또 dfs가 진행된다.

 

 

====================================

 

 

 

 

KAKT
XEAS
YRWU
ZBQP

 

 

3) 

(2,1)의 위치에서 좌,우,위,아래 방향으로 다음 글자인

E가 있는 위치 (1,1) 에서 또 dfs가 진행된다.

 

 

=======================================

 

 

4) 

KAKT
XEAS
YRWU
ZBQP

 

(1,1)의 위치에서 좌,우,위,아래 방향으로 다음 글자인

A가 있는 위치 (0,1) 에서 또 dfs가 진행된다.

 

============================================

 

5) 

KAKT
XEAS
YRWU
ZBQP

 

(0,1)의 위치에서 좌,우,위,아래 방향으로 다음 글자인

K가 있는 위치 (0,2) 에서 또 dfs가 진행된다.

 

 

==========================================

 

그런데 이제 마지막 글자이므로 

이 경우는 값 1을 리턴한다.

그래서 dp[0][2][4] = 1 이다. 

즉 위치 (0,2) 에서 A를 만들 수 있는 경우의 수가 1이다.

 

그러면 dp[0][1][3] 에는 1이 더해지게 된다. 

즉, 위치 (0,1) 에서 AK를 만들 수 있는 경우가 1만큼 증가함.

 

 

 

이런 식으로 아래에서부터 위로 올라가는 형식으로 해결하면 된다. 

 

 

 

 

맨 처음 dp 배열을 모두 -1 로 채운 이유는 방문하지 않았음을 표현하는 것이다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {
	
	static char[][] board;
	static int dp[][][];
	static int N;
	static int M;
	static int K;
	static String word;
	
    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());
          board = new char[N][M];
	
		  for (int i = 0; i < N; i++) {
		          String input = br.readLine();
		         
		          for (int j = 0; j < M; j++) {
		              board[i][j] = input.charAt(j);
		          }
		      }	  
		  
		  	word = br.readLine();
			
			   dp = new int[N][M][word.length()];
			   for (int i = 0; i < N; i++) {
		              for (int j = 0; j < M; j++) {
		                  Arrays.fill(dp[i][j], -1);
		              }
		          }
			  long count = 0;
			  for(int i=0; i<N; i++) {
				  for(int j =0; j<M; j++) {
					  
					  if(board[i][j] == word.charAt(0)){
					
						  count+=dfs(i,j,0);						  
					  }						  
			  }
    }
    
  System.out.println(count);
     
}
    

    public static int dfs(int x, int y, int length) {
	
    	
    	if(dp[x][y][length]!=-1) {    	
    		return dp[x][y][length];
    		
    	}
   
    	if(length == (word.length()-1)) {    	
    		return dp[x][y][length]=1;
    		
    	}
    	
    	dp[x][y][length] = 0;
    	
    	int dx[] = {-1,1,0,0};
    	int dy[] = {0,0,-1,1};
	
    	for(int i=1; i<=K; i++) {
	    	for(int j=0; j<4; j++) {
	    		
	    		int nextX = x + dx[j]*i;
	    		int nextY = y + dy[j]*i;	    		
	    		
	    		if(nextX>=0 && nextX<N && nextY>=0 && nextY<M) {
	    		
	    			if (board[nextX][nextY] == word.charAt(length+1)){
	    				
	    				dp[x][y][length] += dfs(nextX, nextY,length+1);    				
	    			}    			
	    		}
	    	}
    }
    	
    	
    	return dp[x][y][length];
  }
}

 

 

참고 블로그 : [알고리즘/백준] 2186번: 문자판 (JAVA) (velog.io)

[알고리즘/백준] 2186번: 문자판 (JAVA)