[ 백준 2186 ] 문자판 (C++)

백준의 문자판(2186) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 처음 문제를 보고, BFS혹은 DFS로 찾고자 하는 문자열의 인덱스 번호에 맞게 알파벳만 찾아가는 식으로 탐색을 진행하면 정답을

   도출해낼 수 있을줄 알았다. 하지만 이렇게 구현할 경우, 정답은 도출해 낼 수 있지만, 시간초과가 떴다.

   따라서, 이 부분을 해결하기 위해서 DFS + Dynamic Programming 을 합쳐서 구현해 보았다.

   DFS와 DP를 어떻게 접해서 구현해야 하는지 차근차근 알아보도록 하자.

   먼저, 사용한 변수부터 알아보자. 핵심 변수로는 DP[][][] 3차원 배열이 있다.

   DP[a][b][c] = d의 의미는 "(a, b)에 존재하는 알파벳을 찾고자하는 문자열의 'c'번 인덱스로 설정했을 때, 나올 수

   있는 정답의 갯수 갯수는 d개입니다" 이다.

   정확하게 무슨 말 뜻인지 모르더라도 괜찮다. 계속 해결해나가보자.

   위의 배열을 어떻게 사용할 것이고, 왜 DP를 쓰면 시간초과를 방지할 수 있는지 알아보도록 하자.

  

   위와 같은 맵에서 'ABCDE'라는 문자열을 찾아야 한다고 가정해보자.

   먼저 시작점으로 잡을 수 있는 좌표로는 (2, 0) , (2, 2), (3, 1) 에 존재하는 A가 있다. 2중 for문의 순서상, (2, 0)에 있는 A좌표가

   가장 먼저 실행되니, (2, 0)에 있는 A부터 보도록 하자.

   (2, 0)에 갈 수 있는 A의 경우 'ABCDE'를 만들 수 있는 경로를 먼저 생각해보자.(앞에서 부터 인덱스번호 0~ 4번)

   1. (2, 0) → (2, 1) → (1, 1) → (0, 1) → (0, 2)

   2. (2, 0) → (2, 1) → (1, 1) → (1, 2) → (0, 2)

   이렇게 2가지 방법이 있다. 가장먼저 (2, 0)에 존재하는 'A'에서 DFS를 실행시키게 되면 찾고자 하는 그다음 문자열의 인덱스

   번호인 1번 문자를 찾으러 갈 것이다. 즉, 알파벳 'B'를 찾아 나서게 될 것이다.

   (2, 0)에서는 'B'로 갈 수 있는 방법이 총 2가지가 있다. (2, 1)로 가는 방법과 (3, 0)으로 가는 방법 !

   먼저 (3, 0)으로 향한 경우를 생각해보자. (3, 0)에 있는 'B'에서는 그 다음 문자인 'C'를 찾을 수가 없다. 즉, (2, 1)에 있는

   'B'를 1번 인덱스로 설정했을 경우, 'ABCDE'를 만들 수 있는 경우는 0개 입니다 가 된다.

   즉, DP[3][0][1] = 0 이 된다는 것이다.

   이제 (2, 1)로 가보도록 하자. (2, 1)에 존재하는 'B'에서는 (1, 1)에 있는 'C'로 나아갈 수 있다.

   (1, 1)에 있는 'C'에서는 'D'로 갈 수 있는 방법이 2가지가 있다.

   먼저, (0, 1)에 존재하는 'D'로 간 경우를 생각해보자. (0, 1)에서 (0, 2)에 존재하는 'E'를 찾아서 'ABCDE'를 완성하게 된다.

   즉, 마지막 문자를 찾게되는 순간, 지금까지 온 경로에 있는 모든 값들이 + 1이 되게 된다.

   위에서 말한 DP[][][]의 개념에 맞게 다시 말해보자면

   (2, 0)을 0번째 인덱스로 설정했을 때, 'ABCDE'를 찾는 경우의 수는 1개입니다.

   (2, 1)을 1번째 인덱스로 설정했을 때, 'ABCDE'를 찾는 경우의 수는 1개입니다

    ..... 이런식으로 쭉 가서 (0, 2)를 4번째 인덱스로 설정했을 때, 'ABCDE'를 찾는 경우의 수는 1개 입니다 가 된다.

   그렇다면 이제 (1, 1)에 존재하는 C에서 (0, 1)이 아닌 (1, 2)로 가보도록 하자. (1, 2)에서도 (0, 2)로 향할 수 있기 때문에

   위와 같이 모든 지금까지 왔던 경로의 값들이 모두 + 1이 되게 된다.

   즉, (2, 0), (2, 1), (1, 1), (1, 2), (0, 2) 이 5개의 값들이 +1씩 되게된다.

   지금까지 했던 설명이 첫번째 문자인 'A'를 (2,0)으로 잡았을 때의 경우이다.

   그렇다면, (2, 2)에 존재하는 'A'를 첫번째 문자로 잡으면 어떻게 될까??

   (2, 2)에서  B를 찾기 위해서 (2, 1)에 존재하는 'B'로 탐색을 진행하게 될 것이다. 그렇다면 우리는 여기서, 또 모든 경로를

   탐색해줘야 할까?? 아니다. 그렇지 않다.

   우리는 기존에 (2, 0)에서부터 탐색을 하면서 (2, 1)에 존재하는 'B'를 1번째 인덱스로 삼았을 때의 경우의 수가 '2'가 나온다는

   것을 알고 있다. 즉, 가봤자 똑같이 2가지 경우라는 결과값을 도출해낼 텐데, 또 탐색을 할 필요가 없는 것이다.

   따라서, 위의 코드의 결과는 6이 될 것이다.

   (2, 0)을 시작점으로 했을 때 'ABCDE'를 찾는 경우 = 2 , (2, 2)를 시작점을 했을 때 = 2, (3, 1)을 시작점으로 했을 때 = 2

  

   실제 위의 케이스를 넣었을 경우, 실행결과 창이다.

   그렇다면, 일반 BFS or DFS와 어떤 경우가 다르길래 시간을 더 줄일 수 있는지 한번 생각해보자.

   일단 DFS로 풀이를 진행해보았다면, (2, 0)에 존재하는 A에서 갈 수 있는 모든 루트 탐색 + (2, 2)에 존재하는 A에 갈 수 있는

   모든 루트 탐색 + (3, 1)에 존재하는 A에 갈 수 있는 모든 루트 탐색을 통해서 중복된 결과값들에 대해서 같은 탐색을

   반복하게 된다. 이를 DP를 적용시켜서 중복된 탐색을 줄였기 때문에 시간을 줄일 수 있다.

 

2) 그렇다면 이제부터 위의 내용을 코드로 구현해보도록 하자.

   먼저 DP[][][] 배열의 모든 인덱스의 초기값은 -1로 설정해 두었다. 0이 아닌 -1로 둔 것은, 이 문제에서 DP[][][] = 0 이라는 것

   은, 해당 좌표에 있는 값을 특정 인덱스 번호로 설정했을 때, 나올 수 있는 경우의 수는 0이라는 의미를 갖는 값이기 때문에, -1로

   초기값을 설정해 주었다.

   그렇다면, 우리가 1)에서 봤듯이, (2, 1)에 존재하는 'B'까지만 오면 모든 경우의 수를 다 알 수가 있었다.

   즉, (2,1)에 존재하는 'B'로 왔을 때는 더 이상 탐색을 하지 않아도 됬었고, (3, 0)에 존재하는 B로 갔을 때는 보나마나 이 길로 가면

   어차피 결과는 0이다 라는 것을 알 수 있었는데, 이를 어떻게 표시를 할지 생각을 해보자.

   탐색을 하다 보면, 이미 탐색한 지점은 최소 0의 값을 갖게 된다. 즉 -1의 값은 안가지게 된다는 의미이다. 해당 지점으로 갔을 때

   결과를 도출해 낼 수 없으면 0이기 때문에, 반대로 어떤 결과라도 없게되면 그것보다 더 큰 값을 가지게 될것이다.

   중요한건 초기값인 '-1'의 값을 가지지 않게 된다는 것이다.

   즉, DP[][][] != -1 인 좌표들에 대해서는 더이상 탐색을 하지 않아도 된다. 해당, DP[][][] 배열의 값을 반환해주면 그만이다.

   또한, 무한대의 탐색을 방지하기 위해서, 탐색하고자 하는 인덱스 번호가 찾고자 하는 문자열의 길이보다 더 커진다면

   그대로 종료시키도록 해 주었다. 마지막 문자열까지 모두 찾았다면 더 이상의 탐색은 하지 않아도 되기 때문이다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<string>
 
#define endl "\n"
#define MAX 100
using namespace std;
 
int N, M, K, Answer;
char MAP[MAX][MAX];
int DP[MAX][MAX][80];
 
string Dest;
int Dest_Len;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
 
void Input()
{
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
        }
    }
    cin >> Dest;
    Dest_Len = Dest.length();
    memset(DP, -1, sizeof(DP));
}
 
int DFS(int x, int y, int Idx)
{
    if (DP[x][y][Idx] != -1) return DP[x][y][Idx];
    if (Idx >= Dest_Len) return 1;
 
    DP[x][y][Idx] = 0;
    for (int i = 0; i < 4; i++)
    {
        for (int k = 1; k <= K; k++)
        {
            int nx = x + dx[i] * k;
            int ny = y + dy[i] * k;
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (MAP[nx][ny] != Dest[Idx]) continue;
 
            DP[x][y][Idx] = DP[x][y][Idx] + DFS(nx, ny, Idx + 1);
        }
    }
    return DP[x][y][Idx];
}
 
void Solution()
{
    char Temp = Dest[0];
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (MAP[i][j] == Temp)
            {
                Answer = Answer + DFS(i, j, 1);
            }
        }
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}