SWEA-1861 정사각형 방

일반적인 BFS로 진행했더니, 제한시간 초과가 나와서 메모이제이션을 통해 진행했다!

동일한 숫자를 return 했을 경우 더 작은 수로 갱신해서 출력해주었다.

#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int arr[1010][1010];
int ans[1010][1010];
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
int st = 0;

int dfs(int x, int y) {
	if (ans[x][y] != 0) return ans[x][y];
	ans[x][y] = 1;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (arr[nx][ny] == arr[x][y] + 1) {
			ans[x][y] = ans[x][y] + dfs(nx, ny);
		}
	}
	return ans[x][y];
}

int main()
{
	int tc;
	cin >> tc;
	for (int T = 1; T <= tc; T++) {
		memset(ans, 0, sizeof(ans));
		int n;
		cin >> n;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> arr[i][j];
			}
		}

		int maximum = -1;
		int maxarr = -1;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int cnt = dfs(i, j);
				if (cnt > maximum) {
					maximum = cnt;
					maxarr = arr[i][j];
				}
				else if (cnt == maximum) {
					if (maxarr > arr[i][j])	maxarr = arr[i][j];
				}

			}
		}
		cout << "#" << T << " " << maxarr << " " << maximum << '\n';
	}
	return 0;
}