백준 2186. 문자판 [실패]

1.실패 원인

당연히 bfs로 접근했다. 내 알고리즘 지식으로는 당연히 모든 방향으로 움직이면서 특정 타겟 기준을 만족시켰을 때 값들을 구하는 문제였기에 bfs로 풀었지만, 해당 문제는 방문 여부를 제한하지 않고 최소 경로가 아닌 가능한 모든 경우를 따지는 문제였기에 꼭 bfs 문제는 아니었던 것 같다.

 

내가 작성한 코드가 예시 문제는 통과시켜줬지만, 백준 사이트에 집어넣었을 땐 메모리 초과가 발생했다. 비슷한 오류를 발생시킨 글들을 보니 해당 문제를 bfs로 풀어버리면 아까 말한 visit 문제 때문에 큐에 과도한 메모리를 사용하게 되어 오류를 발생시키는듯 하다.

 

따라서, 이 문제는 bfs가 아닌 dfs + dp 문제로 귀결된다. 나는 모든 경우에 대해 큐에 넣는 생각을 했지만, 타겟 문자열이 주어지는 문제이기 때문에 바로 다음 찾아야 할 문자가 무엇인지 알 수 있다. 그래서, 완전탐색 방식인 방법을 찾을떄 까지 모든 경우 탐색(애초에 방문경로 제한이 없기에 완탐 방식은 굉장히 많은 시간을 소요할 것을 예상)이 아니라 해당 포지션의 문자가 타겟 문자와 일치하면 타겟의 다음 문자 (idx +1)에 대해 재귀적으로 탐색해야한다.

 

dp도 사용된 것을 보아 일반적인 방식으로의 dfs 문제도 메모리 초과를 일으키는 것 같다. 재밌는 부분은 참조자를 통해 특정 주소의 배열값도 변경시켜주는 모습을 보이고 있다.

 

2.작성 코드

#include <iostream> 
#include <string>
#include <vector>
#include <cstring>
using namespace std;
const int MAX = 100;
const int MAX_LENGTH = 80;
typedef struct { int y, x; }Dir;
Dir moveDir[4] = { { 1, 0 },{ -1, 0 },{ 0, 1 },{ 0, -1 } };
int N, M, K; int result; string target; string board[MAX]; 
int cache[MAX][MAX][MAX_LENGTH]; int func(int y, int x, int idx)
{ 
int &result = cache[y][x][idx]; 
if (result != -1) 
{ return result; } 
if (idx == target.length()) 
{ return 1; } result = 0;
for (int k = 0; k < 4; k++) 
{ int tempY = y; int tempX = x; 
for (int i = 0; i < K; i++) 
{ 
int nextY = tempY + moveDir[k].y;
int nextX = tempX + moveDir[k].x;
if (nextY < 0 || nextY >= N || nextX < 0 || nextX > M) { break; } 
if (board[nextY][nextX] == target[idx]) 
{ 
result += func(nextY, nextX, idx + 1); } 
tempY = nextY; tempX = nextX; 
} 
} 
return result; 
} 
int main(void) { 
ios_base::sync_with_stdio(0);
cin.tie(0); 
cin >> N >> M >> K;
for (int i = 0; i < N; i++) { 
cin >> board[i]; 
} 
cin >> target; 
vector<pair<int, int>> start; 
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) { 
if (board[i][j] == target[0]) {
start.push_back({ i, j }); } } } 
memset(cache, -1, sizeof(cache)); 
for (int i = 0; i < start.size(); i++) {
int y = start[i].first; 
int x = start[i].second; 
result += func(y, x, 1); 
} 
cout << result << "\n"; return 0; }

// 출처: https://jaimemin.tistory.com/1285 [꾸준함]

3.참고 코드

jaimemin.tistory.com/1285

백준 2186번 문자판

4. 해결 방안

저번 문제를 통해 2차원 배열을 string으로 표현하였고 bfs 관점으로 보면 답을 도출할 수 있는 수준의 알고리즘도 잘 작성했다. 문제는 이 문제가 bfs를 통해 해결하는 것이 아니라는 점.. 정확히는 cache질을 해줘야 한다는 것이다.