인프런 커뮤니티 질문&답변

dfs 방식으로 풀었는데 메모리초과가 발생해 질문드립니다.

재귀함수이다보니 함수호출이 잦아 발생하는거 같은데,

해당 위치에서, 해당 위치에 도달하는 경로 중 가장 많이 이동한 경로만을 탐색하는 방식으로 진행했음에도 불구하고 메모리초과가 발생하다보니 어디가 문제인지 모르겠어서 질문드립니다 ㅜㅜ...

#include <bits/stdc++.h>

using namespace std;

enum
{ E,
  S,
  W,
  N,
};

// moves : 해당 위치에 도착했을 때, 지금까지 내가 몇번 움직였는지를 저장한다.
int table[51][51], moves[51][51];
int n, m;
int dy[4] = {0,1,0,-1}, dx[4] = {1,0,-1,0};

// dfs, 이동 가능한 방향으로 이동하는 함수
void go(int fy, int fx, int y, int x, int cnt)
{	
	// 움직인 횟수 저장
	moves[y][x] = cnt;
	
	for(int i = E; i < N; i++)
	{
		int ny = y + dy[i]*table[y][x], nx = x + dx[i]*table[y][x];

        // 최대 횟수로 이동한 경로만 통과 가능
		if(ny < 0 || nx < 0 || ny >= n || nx >= m || table[ny][nx] == 0 || cnt + 1 < moves[ny][nx]) continue;
        
        // 무한 루프에 빠지게 될 경우, 탈출
		if(fy == ny && fx == nx)
		{
			exit(0);
		}
		go(y, x, ny,nx, cnt + 1);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> n >> m;
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<m; j++)
		{
			char tmp;
			cin >> tmp;
			if(tmp == 'H')
			{
				tmp = '0';
			}
			table[i][j] = tmp - '0';
		}
	}
	
	go(0,0,0,0,1);
	
	cout << *max_element(moves[0], moves[0] + 51*51);		
		
	return 0;
}