[백준] 문자판 (2186번)

문제

알파벳 대문자가 한 칸에 한 개씩 적혀있는 N×M 크기의 문자판이 있다. 편의상 모든 문자는 대문자라 생각하자. 예를 들어 아래와 같은 문자판을 보자.

K	A	K	T
X	E	A	S
Y	R	W	U
Z	B	Q	P

이 문자판의 한 칸(아무 칸이나 상관없음)에서 시작하여 움직이면서, 그 칸에 적혀 있는 문자들을 차례대로 모으면 하나의 단어를 만들 수 있다. 움직일 때는 상하좌우로 K개의 칸까지만 이동할 수 있다. 예를 들어 K=2일 때 아래의 그림의 가운데에서는 'X' 표시된 곳으로 이동할 수 있다.

		X
		X
X	X		X	X
		X
		X

반드시 한 칸 이상 이동을 해야 하고, 같은 자리에 머물러 있을 수 없다. 또, 같은 칸을 여러 번 방문할 수 있다.

이와 같은 문자판과 K, 그리고 하나의 영단어가 주어졌을 때, 이와 같은 영단어를 만들 수 있는 경로가 총 몇 개 존재하는지 알아내는 프로그램을 작성하시오.

위의 예에서 영단어가 BREAK인 경우에는 다음과 같이 3개의 경로가 존재한다. 앞의 수는 행 번호, 뒤의 수는 열 번호를 나타낸다.

• (4, 2) (3, 2) (2, 2) (1, 2) (1, 1)
• (4, 2) (3, 2) (2, 2) (1, 2) (1, 3)
• (4, 2) (3, 2) (2, 2) (2, 3) (1, 3)

입력

첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 영단어가 주어진다. 모든 문자들은 알파벳 대문자이며, 공백 없이 주어진다.

출력

첫째 줄에 경로의 개수를 출력한다. 이 값은 int 범위이다.

---

알고리즘 분류가 bfs로 되어있어서 철썩같이 믿고 풀었다가 틀렸습니다와 메모리초과가 뜬 문제이다.

bfs가 아닌 dfs와 dp를 이용해서 해결해야 한다.

구현은 큰 어려움이 없이 풀 수 있다.

다만 memorization을 할 때 x, y위치 뿐만 아니라 단어의 길이에 따라서도 값을 구해줘야한다. 

즉 visit[x][y][idx] = t 로 표현할 수 있는데 (x,y)에 단어의 길이가 idx일때 가능한 방법이 t가지라는 뜻이다.

이에 주의해서 dfs로 구현하자.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EB%AC%B8%EC%9E%90%ED%8C%90%20(2186%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <cstring>
using namespace std;
int N, M, K, wordLen, ans;
string word;
char map[102][102];
int visit[102][102][81];
int dx[4] = { -1,0,0,1 };
int dy[4] = { 0,-1,1,0 };

int dfs(int x, int y, int idx) {
	if (visit[x][y][idx] != -1) return visit[x][y][idx]; //방문한 지점의 visit 값 반환
	if (idx >= wordLen) return 1; //기저사례, 정답인 경우 가능하다는 의미의 1 반환. 

	visit[x][y][idx] = 0;
	for (int j = 1; j <= K; j++) {
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i] * j;
			int ny = y + dy[i] * j;
			if (nx < 1 || ny <1 || nx > N || ny > M) continue;
			if (map[nx][ny] != word[idx]) continue;
			visit[x][y][idx] += dfs(nx, ny, idx + 1);
		}
	}
	return visit[x][y][idx];
}

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

	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) 
		for (int j = 1; j <= M; j++) 
			cin >> map[i][j];
			
	cin >> word;
	wordLen = word.size();
	memset(visit, -1, sizeof(visit));

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			if (map[i][j] == word[0])
				ans += dfs(i, j, 1);

	cout << ans;
}