[BOJ] 백준 2186 - 문자판

문제 링크

www.acmicpc.net/problem/2186

2186번: 문자판

 

풀이

상태 전개는 DFS로 해도, BFS로 해도 관계없습니다. 위치와 레벨만 잘 고려해준다면요.

 

DP 배열을 다음과 같이 정의합시다.

$\text{D}[x][y][l]$: $(x, y)$칸을 $l$번째 문자로 방문했을 때 가능한 경우의 수

 

값은 다음처럼 채울 수 있습니다.

$\text{D}[x][y][l] = \text{sum(D}[x'][y'][l-1])$

단, $(x', y')$과 $(x, y)$는 인접함, $p[x'][y'] = s[l-1], p[x][y] = s[l]$, $p$는 문자판, $s$는 만들어야 하는 문자열

 

정답 코드

BFS 풀이

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
#define ft first
#define sd second
#define all(x) (x).begin(), (x).end()
using namespace std;
using pii = pair<int, int>;
using vb = vector<bool>;
using vvb = vector<vb>;

int n, m, k;
string p[111], t;
int d[111][111][88];

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

bool isValid(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    queue<pii> q;
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    cin >> t;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (p[i][j] == t[0]) {
                q.emplace(i, j);
                d[i][j][0] = 1;
            }
        }
    }

    int len = 0;
    int ans = 0;
    while (!q.empty()) {
        int qsze = q.size();
        if (++len == t.size()) break;
        while (qsze--) {
            auto[x, y] = q.front();
            q.pop();
            for (int i = 0; i < 4; i++) {
                for (int j = 1; j < k + 1; j++) {
                    int nx = x + dx[i] * j;
                    int ny = y + dy[i] * j;
                    if (!isValid(nx, ny) || p[nx][ny] != t[len]) continue;
                    if (d[nx][ny][len] == 0) q.emplace(nx, ny);
                    d[nx][ny][len] += d[x][y][len - 1];
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            ans += d[i][j][(int) t.size() - 1];
        }
    }
    cout << ans;
}

 

DFS 풀이

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
#define ft first
#define sd second
#define all(x) (x).begin(), (x).end()
using namespace std;

int n, m, k;
string p[111], t;
int d[111][111][88];
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

bool isValid(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}

int go(int x, int y, int len) {
    if (len == t.size()) return 1;
    int &ret = d[x][y][len];
    if (ret != -1) return ret;
    ret = 0;
    for (int i = 0; i < 4; i++) {
        for (int j = 1; j < k + 1; j++) {
            int nx = x + dx[i] * j;
            int ny = y + dy[i] * j;
            if (!isValid(nx, ny) || p[nx][ny] != t[len]) continue;
            ret += go(nx, ny, len + 1);
        }
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    cin >> t;

    int ans = 0;
    memset(d, -1, sizeof(d));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (p[i][j] == t[0]) {
                ans += go(i, j, 1);
            }
        }
    }
    cout << ans;
}