boj, 백준) 2186. 문자판(C / C++)

1. 문제 링크

www.acmicpc.net/problem/2186

2186번: 문자판

2. 문제 개요

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

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

 

3. 문제 힌트

처음에 문제를 읽었을 때 갔던 곳을 또 갈 수 있다는 점에서 DP가 필요하겠구나 라고 생각했다.

일단 dp값은 어떤 블록에 도착했을 때 탐색을 굳이 하지 않아도 알 수 있도록 하는 그런 값이 들어가 있으면 좋겠다.

 

글자를 찾아갈 때 DFS, BFS 2가지의 경우를 생각해볼 수 있는데,

 

BFS 같은경우는 dp를 2차원으로 구성할 수 있다.

DFS 같은 경우는 dp를 3차원으로 구성해야 한다. 순서가 중요하기 때문. cycle방지를 위함. ABCDABC일 때 'A'가 첫 번째인지 5번째인지 구분해야 함.

4. 문제 풀이

DFS풀이는 다른 블로그에서 잘 설명하고 있기 때문에, 비중을 적게 하고 BFS로 하면서 겪었던 문제 위주로 풀이하겠습니다.

 

dp에는 해당 블록 (행, 열) 차원이 기본적으로 들어가야 한다.

우선 BFS로 구현을 했다.

BFS는 순서가 필요 없다. 예를 들면 DFS는 100개가 있으면 1개 찾고 또 1개를 찾는 방식이기 때문에 순서가 필요하다.

BFS는 모두 한꺼번에 딱! 찾기 때문에 dp가 3차원일 필요가 없다. 

 

그래서 굳이.. 메모리를 더 쓰면서 DFS로 구현을 해야 할까.. 싶어서 BFS로 될 때까지 해봤다. BFS 같은 경우는 도중에 오버플로우가 발생할 수 있다. 만약에 80 글자짜리를 찾는다고 가정해보자. 맵은 100x100 모두 'A'로 이루어져 있고 찾는 글자는 'AAAA........ B'이다

이런 경우 79글자까지 모두 맞고 80자에서 다 틀리기 때문에 정답은 0으로 잘 나올 것이다. 그런데 이런 경우 한 5단계쯤부터는 숫자가 급격하게 커지면서 dp값들이 도중에 엄청나게 불어날 것이다.  그래서 이런 오버플로우를 잡을 수 없을까 생각을 하다가.. 그냥 DFS로 한다면 위와 같은 trivial한 case가 없어질 거라 생각하고 DFS로 구현해서 정답을 맞았다.

 

bfs 같은 경우는 가지치기가 빨리 안 되는 게 아쉬웠다. 그리고 이렇게 오버플로우가 생기지 않는 케이스에서는 모두 정답을 뱉어서 오류를 찾는데 아까운 시간을 조금 썼다.

 

DFS로 구성을 하면

일단 어떤 한 칸에서 dfs를 시작하면 거기서 시작해서 요구하는 글자와 비교를 해나가기 때문에 BFS처럼 도중에 값이 엄청나게 늘어날 수가 없다. 대신에 cycle이 돌 수 있기 때문에 몇 번째인지를 나타내는 dp가 필요하다.

 

BFS에서의 시행착오를 위주로 서술했습니다. DFS풀이는 다른 분들이 이미 잘해놓으셔서..

저처럼 BFS로도 짤 수 있을 것 같은데 왜 안될까 하시는 분들에게 도움이 되었으면 좋겠습니다.

5. 코드

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

char map[100][100], str[80];
int dp[100][100][80];
int n, m, k, ans, len;
const int dx[] = { 1,-1,0,0 };
const int dy[] = { 0,0,1,-1 };

int dfs(int y, int x, int depth)
{
	//boundary
	if (y < 0 || x < 0 || y >= n || x >= m)
		return 0;
	//base
	if (map[y][x] != str[depth])
		return dp[y][x][depth] = 0;
	//memoization
	if (dp[y][x][depth] != -1)
		return dp[y][x][depth];
	else
		dp[y][x][depth] = 0;

	for (int dir = 0; dir < 4; ++dir){
		for (int w = 1; w <= k; ++w) {
			int nx = x + dx[dir] * w;
			int ny = y + dy[dir] * w;
			if (depth + 1 == len)
				return dp[y][x][depth] = 1;
			else
				dp[y][x][depth] += dfs(ny, nx, depth + 1);
			
		}
	}
	return dp[y][x][depth];
}

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

	cin >> n >> m >> k;
	for (int i = 0; i < n; ++i)
		cin >> map[i];
	cin >> str;
	len = strlen(str);
	memset(dp, -1, sizeof(dp));

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
				ans += dfs(i, j, 0);

	cout << ans;

	return 0;
}

 

6. 결과

틀리기 싫어서 위 5번 코드처럼 구현하면 느린 걸 알면서도 저렇게 구현했다.

그냥 조건문을 반복문 안으로 넣어서 시간을 조금 더 줄여봤다