[백준문제풀이] 2186 문자판

 

풀이일시 : 2020-11-15

​

 

문제 :

알파벳 대문자가 한 칸에 한 개씩 적혀있는 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자 이하의 영단어가 주어진다. 모든 문자들은 알파벳 대문자이며, 공백 없이 주어진다.

ex)

4 4 1

KAKT

XEAS

YRWU

ZBQP

BREAK

​

​

출력 :

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

ex)

3

​

​

풀이 :

DFS + DP문제. DFS로만 BP구성할경우 시간초과가 뜬다. DP로 효율적이게 만들어줘야한다.

기본적으로 DFS를 원하는 문자열이 완성될때까지 돌려준다.

 

dbstndi6316.tistory.com/64

[기본문제풀이] DFS 깊이우선탐색

dbstndi6316.tistory.com/35

[개념정리] DP 동적프로그래밍

#include <iostream>
#include<string>
using namespace std;

int N, M, K;
char map[100][100];
string word;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int dp[100][100][80]; // =t 라면 (x,y)에 단어의 길이가 idx 일때 가능한 방법이 t가지라는 것
//dp는 즉 지금까지 사용하던 visit이다

int dfs(int y, int x, int idx) { //처음들어올땐 idx 1로 들어온다.
	if (idx == word.length()) { //idx ++하며 그 지점에서 다 탐색완료했다면
		return 1;
	}
	if (dp[y][x][idx] != -1)  //이미 값이 저장된 경우
		return dp[y][x][idx];
	else {
		dp[y][x][idx] = 0; //0으로 만들어준다.
		for (int i = 1; i <= K; i++) { //K번 반복해줄거다
			for (int j = 0; j < 4; j++) { //4방향 탐색할거다
				int ny = y + dy[j] * i; //상하좌우 좌표
				int nx = x + dx[j] * i; //상하좌우 좌표
				if (ny < 0 || ny >= N || nx < 0 || nx >= M) //범위안맞으면
					continue; //다음 반복문으로
				if (map[ny][nx] == word[idx]) { //그 글자와 맞으면
					dp[y][x][idx] += dfs(ny, nx, idx + 1); //한 시작점에서출발해서 만들수있는개수 쌓일것
				}
			}
		}
	}
	return dp[y][x][idx]; //한 시작점에서 출발하여 만들 수 있는 총 갯수 반환
}

int main() {
	scanf("%d %d %d", &N, & M, &K);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}
	cin >> word; //이 영단어를 만들 수 있는 경로가 총 몇개인지
	memset(dp, -1, sizeof(dp)); //dp 초기화
	int result = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == word[0]) { //string에서 [0]은 첫글자라는거
				result += dfs(i, j, 1); //모든 시작점(w[0])에서 출발하여 만들수있는 갯수 합한다
			}
		}
	}
	printf("%d", result);
	return 0;
}