[ 백준 ] 2186 / 문자판

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
88/228
post-thumbnail

# Appreciation

/*
 * Problem :: 2186 / 문자판
 *
 * Kind :: Dynamic Programming
 *
 * Insight
 * - 브루트 포스로 풀려고 했다가 틀렸다
 *   + max(N)=100 이고 max(M)=100 이라 상대적으로 작아보이지만
 *     K 와 한글자로 이루어진 영단어를 생각해보면 엄청난 시간복잡도가 나오게 된다
 *     # 최악의 경우를 생각해보면
 *       N=100, M=100, K=5 이고
 *       모든 문자판이 'B'로 이루어져 있으며
 *       영단어=BBB...BBB(80자) 라고 하자
 *       이경우, 시간복잡도는 O(NM*(20^80)) 가 나온다
 *       -> 당연히 시간초과다
 *
 * - 예제 입력 1 과 같이 주어졌다고 하자
 *   문자판에서 (1,1) 이 'K' 이며 주어진 영단어 "BREAK" 의 마지막 글자도 'K' 이다
 *   가능한 모든 경우중에서 (1,1) 의 'K' 로 끝나는 경우의 수를 알아낼 수 없을까?
 *   + 이를 다음과 같이 표현할 수 있다
 *     dp[1][1][4] = (1,1) 의 문자를 마지막문자로 하며,
 *                   영단어.substr(0,5) 를 만들 수 있는 경우의 수
 *     # 이를 일반화하면
 *       dp[i][j][idx] = (i,j) 의 문자를 마지막문자로 하며
 *                       영단어.substr(0,idx+1) 을 만들 수 있는 경우의 수
 *       -> 그냥 찾으면 시간초과지만,
 *          각 칸의 글자가 주어진 영단어에서 몇번째에 위치하는 것이 가능한지
 *          그 경우의 수를 알아낼 수 있다면 DP 를 이용해서 최적화가 가능하다!
 *          => (i,j) 에서 이동가능한 임의의 칸을 (y,x) 라 하면
 *             dp[i][j][idx] += dp[y][x][idx-1]
 *
 * Point
 * - 최악의 경우를 생각하는 것이 중요하다
 *
 * - i번째 글자는 인덱스로는 (i-1)이다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source


#include <iostream>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables
int N, M, K;
char A[100][100];
int dp[100][100][80];
string W;
int dy[4] = {+1, 0, 0, -1};
int dx[4] = {0, +1, -1, 0};

// Set up : Functions Declaration
bool isValid(int y, int x);
int f(int cy, int cx, int idx);

int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    cin >> N >> M >> K;
    for (int i=0; i<N; i++)
        for (int j=0; j<M; j++)
            cin >> A[i][j];
    cin >> W;

    // Process
    memset(dp, -1, sizeof(dp));
    int ans = 0;
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            /* (i,j) 의 문자와 영단어의 마지막 문자가 같다면 */
            if (A[i][j] == W.back()) {
                /* (i,j) 의 문자를 마지막으로 하며 영단어를 만들 수 있는 경우의 수를 더함 */
                ans += f(i, j, W.length()-1);
            }
        }
    }

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
bool isValid(int y, int x)
/* 주어진 좌표 (y,x) 가 유효하면 true 를 반환, 그 외 false 를 반환 */
{
    return y >= 0 && y < N && x >= 0 && x < M;
}

int f(int cy, int cx, int idx)
/* dp[cy][cx][idx] 값을 반환
 * = (cy,cx) 의 문자를 마지막문자로 하며,
 *   영단어.substr(0,idx+1) 을 만들 수 있는 경우의 수를 반환 */
{
    if (idx == 0) return 1; /* 가능한 경우를 찾음 */
    if (dp[cy][cx][idx] != -1) return dp[cy][cx][idx];

    dp[cy][cx][idx] = 0;
    for (int i=0; i<4; i++) {
        for (int k=1; k<=K; k++) {
            int py = cy + k*dy[i];
            int px = cx + k*dx[i];
            /* (py,px) 가 이동가능하지 않으면 넘어감 */
            if (not(isValid(py, px))) break;
            /* (px,py) 에 써진 글자가 영단어의 idx번째 글자와 일치하지 않으면 넘어감 */
            if (not(A[py][px] == W[idx-1])) continue;
            dp[cy][cx][idx] += f(py, px, idx-1);
        }
    }

    return dp[cy][cx][idx];
}
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글