2186번

2186번 - 문자판

이 문제는 처음에 DFS를 통해서 완전탐색으로 풀었는데, 시간 초과가 발생

DP로 문제를 해결하였다.

찾아야하는 문자열과 같을 때 dfs를 돌렸고, 그렇게 해서 처음에 시간 초과가 났다.

중복되는 지점을 찾다보니, 어떤 점에서 find_idx 가 같으면 굳이 계산할 필요가 없다는 걸 깨달았다.

D[find_idx][x][y] = x,y 에 도착했을 때 다음에 찾아야할 값이 goal[find_idx] 인 경우의 수

라고 점화식을 만들었다.

<오답 코드 - 시간 초과>

#include<iostream>
#include<string>
 
using namespace std;
 
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int N, M, K;
int ans = 0;
string goal;
char map[101][101];
 
void dfs(int x, int y,int find_idx)
{
    if (goal.size() == find_idx)
    {
        ans += 1;
        return;
    }
 
    for (int i = 1; i <= K; i++)
    {
        for (int d = 0; d < 4; d++)
        {
            int nx = x + (dx[d] * i);
            int ny = y + (dy[d] * i);
            if (nx >= 0 && ny >= 0 && nx < N && ny < M && map[nx][ny] == goal[find_idx])
            {
                dfs(nx, ny, find_idx + 1);
            }
        }
    }
}
int main()
{
 
    cin >> N >> M >> K;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> map[i][j];
        }
    }
 
    cin >> goal;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (map[i][j] == goal[0])
            {
                dfs(i, j,1);
            }
        }
    }
 
    cout << ans << endl;
    return 0;
}

<정답 코드>

#include<iostream>
#include<string>
using namespace std;
 
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int D[80][101][101];
int N, M, K;
int ans = 0;
string goal;
char map[101][101];
 
int dfs(int x, int y,int find_idx)
{
    if (find_idx == goal.size())
    {
        return 1;
    }
 
    if (D[find_idx][x][y] > 0)
    {
        return D[find_idx][x][y];
    }
 
    for (int i = 1; i <= K; i++)
    {
        for (int d = 0; d < 4; d++)
        {
            int nx = x + (dx[d] * i);
            int ny = y + (dy[d] * i);
            if (nx >= 0 && ny >= 0 && nx < N && ny < M && map[nx][ny] == goal[find_idx])
            {
                D[find_idx][x][y]+=dfs(nx, ny, find_idx + 1);
            }
        }
    }
 
    return D[find_idx][x][y];
}
int main()
{
 
    cin >> N >> M >> K;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> map[i][j];
        }
    }
 
    cin >> goal;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (map[i][j] == goal[0])
            {
                ans +=dfs(i, j,1);
            }
        }
    }
 
    cout << ans << endl;
    return 0;
}