[Algorithm]Baekjoon 2186번 : 문자판

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

2186번: 문자판

 
struct Node
{
    int y;
    int x;
};
 
int n, m, k;
string target;
int dirs[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
char arr[101][101];
int dp[101][101][81] = { 0 };
vector<Node> starts;
 
int DFS(int y, int x, int targetIndex)
{
    if (dp[y][x][targetIndex] != -1) return dp[y][x][targetIndex];
    if (targetIndex == target.size() - 1) return 1;
 
    int count = 0;
 
    for (int i = 0; i < 4; ++i)
    {
        for (int j = 1; j <= k; ++j)
        {
            int nextY = y + dirs[i][0] * j;
            int nextX = x + dirs[i][1] * j;
 
            if (nextY < 0 || nextY >= n) continue;
            if (nextX < 0 || nextX >= m) continue;
            if (arr[nextY][nextX] != target[targetIndex + 1]) continue;
 
            count += DFS(nextY, nextX, targetIndex + 1);
        }
    }
 
    return dp[y][x][targetIndex] = count;
}
 
int main()
{
    ios::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 >> target;
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (arr[i][j] == target[0])
            {
                starts.push_back({ i,j });
            }
        }
    }
 
    int answer = 0;
    memset(dp, -1, sizeof(dp));
    
    for (int i = 0; i < starts.size(); ++i)
    {
        answer += DFS(starts[i].y, starts[i].x, 0);
    }
 
    cout << answer;
}
 

 

dp + 그래프탐색 문제이다.

특정단어가 주어지는데, 해당단어를 만들기위한 루트의 개수를 구하는 문제로, 은근히 흔한 유형중 하나이다.

같은곳에 재방문이 가능하며, 상하좌우 이동할 때 1칸씩이 아닌 최대 k칸 이동이 가능하다.

특정단어를 만들어야 하니, 단어의 시작지점을 저장한다음 해당지점으로 DFS를 수행한다.

한 뎁스마다 단어의 인덱스가 +1씩 되며, 끝지점에 도달했을 때 하나의 경로가 완성됐기 때문에 1을 리턴한다.

 

이때, arr의 각 칸에 타겟단어의 인덱스에 따른 루트개수를 저장해준다.

즉 dp[i][j][k]는 arr[i][j]에 특정단어의 k번째 인덱스로 도착했을 때 타겟단어를 완성시킬 수 있는 경로의 수이다.

그리고 dp값 초기화는 반드시 0 이외의 값으로 해줘야한다. -1이든 뭐든

특정위치 i,j에 k번째 인덱스의 값이 0인경우가 존재하기 때문이다. 즉, 탐색을 수행한 후에야 해당 지점에 타겟단어로의 경로가 없다는걸 판별할 수 있는데, 처음부터 0으로 초기화되어있으면 값이 겹쳐버려서 중복탐색을 수행하기 때문이다.