[백준] 2186 | 문자판 [C]

문제

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

 

접근

사실 파이썬으로 문제를 풀기 시작했는데 시간 초과가 계속 발생해서 C언어로 바꿔서 제출했다. 간만에 C언어 쓰니까 반가웠고...

개인적으로 C를 좋아한다.

dfs + dp로 문제를 해결했다.

 

코드

#include <stdio.h>
#include <string.h>

int n, m, k;
int L;
char board[101][101];
char word[81];
int dp[101][101][81];
int d[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int dfs(int x, int y, int wi){
    if(wi == L){
        return 1;
    }
    if(dp[x][y][wi] != -1){
        return dp[x][y][wi];
    }
    
    dp[x][y][wi] = 0;
    for(int di = 0; di < 4; di++){
        int nx = x;
        int ny = y;
        for(int w = 1; w < k+1; w++){
            nx += d[di][0];
            ny += d[di][1];
            if(0 <= nx && nx < n && 0 <= ny && ny < m && board[nx][ny] == word[wi]){
                dp[x][y][wi] += dfs(nx, ny, wi+1);
            }
        }
    }

    return dp[x][y][wi];
}

int main(){
    int cnt = 0;
    memset(dp, -1, sizeof(dp));

    scanf("%d %d %d", &n, &m, &k);
    for(int i = 0; i < n; i++){
        scanf("%s", board[i]);
    }
    scanf("%s", word);
    L = strlen(word);	//word 길이

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
        	//문자판의 글자가 영단어의 첫 글자와 같은 경우 탐색 시작
            if(board[i][j] == word[0]){
                cnt += dfs(i, j, 1);
            }
        }
    }

    printf("%d", cnt);
}