SWE 정사각형 방

dfs로 풀었는데 모든 위치에서 dfs를 돌려야한다는게 처음에는 너무 오랜시간이 걸리지 않을까 걱정되었다.

dfs에 처음 시작위치를 저장하여 최댓값을 갱신하여 정답배열에 저장한다. 또한 모든 정답배열 중 최댓값을 답으로 출력해주었다. 

package day0806;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Square {
	static int[][] arr;
	static int[][] ans;
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, -1, 0, 1 };

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int test = Integer.parseInt(bf.readLine());
		for (int t = 1; t <= test; t++) {
			int n = Integer.parseInt(bf.readLine());
			arr = new int[n + 1][n + 1]; //위치마다 적힌 수
			ans = new int[n + 1][n + 1]; //최대 이동 수
			int max = -1; //최댓값
			int mx = 0, my = 0; //최댓값일 떄의 인덱스

			for (int i = 0; i < n; i++) {
				String s = bf.readLine();
				StringTokenizer st = new StringTokenizer(s);
				for (int j = 0; j < n; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
				} 
			}

			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					dfs(i, j, i, j, n, 1);
				}
			}
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (max < ans[i][j]) { //최댓값 발견
						my = i;
						mx = j;
						max = ans[i][j];

					} else if (max == ans[i][j] && arr[i][j] < arr[my][mx]) {//최댓값과 같고 더 작은 적힌 수 갱신
						my = i;
						mx = j;
					}
				} 
			}
			System.out.println("#" + t + " " + arr[my][mx] + " " + max);
			max = 0;
		}
	}

	static boolean isIn(int y, int x, int n) { //벗어나면 false리턴
		if (y < 0 || x < 0 || y >= n || x >= n)
			return false;
		return true;

	}

	static void dfs(int cury, int curx, int y, int x, int n, int cnt) {
						//curx, cury는 현재 방의 위치/ y,x는 처음 시작 방/n은 전체 크기/cnt는 넘어온 방의 수
		for (int i = 0; i < 4; i++) {
			int ny = cury + dy[i];
			int nx = curx + dx[i];
			if (!isIn(ny, nx, n)) //벗어나면 다음으로
				continue;

			if (arr[ny][nx] != arr[cury][curx] + 1) //다음방이 1만큼 커지지 않으면 다음으로
				continue;
			if (cnt + 1 > ans[y][x]) //다음방 찾으면
				ans[y][x] = cnt + 1; //처음 방에 +1 증가
			dfs(ny, nx, y, x, n, cnt + 1);

		}

	}

}