[백준] 2186번 문자판

2186 문자판

문제

---

알파벳 대문자가 한 칸에 한 개씩 적혀있는 N×M 크기의 문자판이 있다. 편의상 모든 문자는 대문자라 생각하자. 예를 들어 아래와 같은 문자판을 보자

K	A	K	T
X	E	A	S
Y	R	W	U
Z	B	Q	P

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

		X
		X
X	X		X	X
		X
		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)

입력

---

첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 영단어가 주어진다. 모든 문자들은 알파벳 대문자이며, 공백 없이 주어진다.

출력

---

첫째 줄에 경로의 개수를 출력한다. 이 값은 int 범위이다.

---

풀이)

dfs로 모든 경우를 확인하는 완전탐색으로 구현시 시간초과.

dp와 dfs 2개 다 이용해서 푸는 문제다.

예전에 특정 위치까지 가는 경로의 수를 구할 때 dp를 사용한 것처럼 풀면 된다.

점화식

dp[i][j][idx] = (i,j) 위치는 문자열 중 인덱스 idx번째까지 일치하는 케이스들의 합

(처음에 dp[i][j] 이중배열로 계산했었는데 이렇게 하면 틀린다.

왜냐면 문자열이 BAAB 이런식으로 중복된 문자를 가지는 문자열일 경우

(a,b)위치의 문자가 A일 때 즉, map[a][b] == 'A'라고 기존 케이스들의 합을 dp[a][b]에

더하기에는 그 'A'가 문자열 중 몇 번째 A인지 모르기 때문에 계산값이 정확하지 않게 된다. 

첫번째 A까지 계산한 값인지, 두번째 A까지 계산한 값인지 모름

=> 문자열 중 어느 위치까지 확인되었던 결과값인지를 알아야하므로 삼중배열 사용)

코드)

#include <stdio.h>
#include<iostream>
#include<string>
#include<string.h>
using namespace std;
 
int N, M, K;
char map[100][100];
string word;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int dp[100][100][80];
//처음에 이중배열로 했었는데 생각해보니, 어느 번째 인덱스까지 맞춰서 나온건지 정보가 저장안되었음
//단순히 이중배열로 하면 값을 잘못 리턴받음
//word가 중복 알파벳이 있을 수 있음 BAAB -> 첫번째 계산 뒤
//새로운 B 만난 후 그다음 A만났는데
//첫번째 계산에서 어느 번째로 계산한 A인지 모르고 값을 가져올수도
 
int dfs(int y,int x,int idx) {
    if (idx == word.length()) {
        return 1;
    }
    if (dp[y][x][idx] != -1) return dp[y][x][idx];
    else {
        dp[y][x][idx] = 0;
        for (int i = 1; i <= K; i++) {
            for (int j = 0; j < 4; j++) {
                int ny = y + dy[j] * i;
                int nx = x + dx[j] * i;
                if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
                if (map[ny][nx] == word[idx]) {
                    dp[y][x][idx] += dfs(ny, nx, idx + 1);
                }
            }
        }
    }
    
    return dp[y][x][idx];
}
 
int main() {
    scanf("%d %d %d", &N, &M, &K);
    getchar();
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            map[i][j] = getchar();
        }
        getchar();
    }
    cin >> word;
    memset(dp, -1, sizeof(dp));
    int result = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == word[0]) {
                result += dfs(i, j, 1);
            }
        }
    }
    
    printf("%d", result);
    return 0;
}