[BOJ 2186] 문자판

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

2186번: 문자판

 

- 문제 요약

 

알파벳 대문자가 한 칸에 한 개씩 적혀있는 N×M 크기의 문자판이 있다.

이 문자판의 한 칸(아무 칸이나 상관없음)에서 시작하여 움직이면서, 그 칸에 적혀 있는 문자들을 차례대로 모으면 하나의 단어를 만들 수 있다. 움직일 때는 상하좌우로 K개의 칸까지만 이동할 수 있다. 예를 들어 K=2일 때 아래의 그림의 가운데에서는 'X' 표시된 곳으로 이동할 수 있다.

 

반드시 한 칸 이상 이동을 해야 하고, 같은 자리에 머물러 있을 수 없다. 또, 같은 칸을 여러 번 방문할 수 있다.

이와 같은 문자판과 K, 그리고 하나의 영단어가 주어졌을 때, 이와 같은 영단어를 만들 수 있는 경로가 총 몇 개 존재하는지 알아내는 프로그램을 작성하시오.

위의 예에서 영단어가 BREAK인 경우에는 다음과 같이 3개의 경로가 존재한다. 앞의 수는 행 번호, 뒤의 수는 열 번호를 나타낸다.

• (4, 2) (3, 2) (2, 2) (1, 2) (1, 1)
• (4, 2) (3, 2) (2, 2) (1, 2) (1, 3)
• (4, 2) (3, 2) (2, 2) (2, 3) (1, 3)

(경로의 개수는 2^31-1보다 작거나 같다.)

 

 

- 알고리즘 정리

 

주어진 문자열 S를 경로로 설정하여 가능한 경로의 개수를 카운트해주면 됩니다.

이는 DFS로 구할 수 있고, 경로의 수를 보다 효율적으로 따지기 위해 3차원 DP Table을 만들어줬습니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 101
int n,m,k,dp[MAX][MAX][80],dx[4]={0,0,1,-1},dy[4]={1,-1,0,0},Size,result;
char arr[MAX][MAX];
string s;

int dfs(int x,int y,int idx){
	if(dp[x][y][idx]!=-1){
		return dp[x][y][idx];
	}
	if(idx>=Size){
		return 1;
	}
	dp[x][y][idx]=0;
	for(int i=0;i<4;i++){
		for(int j=1;j<=k;j++){
			int nx=x+dx[i]*j;
			int ny=y+dy[i]*j;
			if(nx<0||ny<0||nx>=n||ny>=m){
				continue;
			}
			if(arr[nx][ny]!=s[idx]){
				continue;
			}
			dp[x][y][idx]=dp[x][y][idx]+dfs(nx,ny,idx+1);
		}
	}
	return dp[x][y][idx];
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m>>k;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>arr[i][j];
		}
	}
	cin>>s;
	Size=s.size();
	memset(dp,-1,sizeof(dp));
    char tmp=s[0];
    for(int i=0;i<n;i++){
    	for(int j=0;j<m;j++){
    		if(arr[i][j]==tmp){
    			result=result+dfs(i,j,1);
			}
		}
	}
	cout<<result<<'\n';
}

코드 제출 결과