https://www.acmicpc.net/problem/2186
2186번: 문자판
첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의
www.acmicpc.net
영어 단어가 "BREAK"처럼 주어지면 문자 판에서 "BREAK"라는 글자가 몇 번 나오는지 구하는 문제입니다.
일단 기본적으로 dfs를 통해 구해주시면 되고, 모든 위치에서 시작할 수 있으니 단어의 첫 알파벳과 일치하는 위치를 시작으로 dfs를 돌려줍니다.
하지만 이 문제는 이동 방법이 상하좌우로 K칸까지 이동할 수 있으므로 훨씬 많은 이동이 발생하므로 dp를 같이 사용해줍니다.
dp[x][y][idx] : (x, y)에 도달하였을 때 현재 찾고자 하는 단어의 인덱스가 idx인 경우의 수
이렇게 놓을 수 있습니다.
문제의 답은 int범위라고 명시되어 있기때문에 long long은 사용하지 않아도 됩니다.
dp를 사용하지 않으면 시간초과가 발생하므로 dp는 필수입니다!!
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
string str;
char list[110][110];
int dp[100][100][81];
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int N, M, K, strLength;
int dfs(int x, int y, int idx) {
if (idx == strLength) return 1;
int &ret = dp[x][y][idx];
if (ret != -1) return ret;
ret = 0;
for (int i = 0; i < 4; i++) {
for (int j = 1; j <= K; j++) {
int nx = x + direct[i][0] * j;
int ny = y + direct[i][1] * j;
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if (list[nx][ny] != str[idx]) continue;
ret += dfs(nx, ny, idx + 1);
}
}
return ret;
}
void func() {
int ans = 0;
memset(dp, -1, sizeof(dp));
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (list[i][j] != str[0]) continue;
ans += dfs(i, j, 1);
}
}
cout << ans << '\n';
}
void input() {
cin >> N >> M >> K;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> list[i][j];
}
}
cin >> str;
strLength = str.size();
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 1577 도로의 개수 (0) | 2021.06.20 |
|---|---|
| boj 4781 사탕 가게 (0) | 2021.06.19 |
| boj 13325 이진 트리 (0) | 2021.06.18 |
| boj 1563 개근상 (0) | 2021.06.02 |
| boj 10800 컬러볼 (0) | 2021.04.09 |