SWEA -1861 정사각형 방

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class swea_1861SquareRoom {
	static int N;
	static int T;
	static int [][] map;
	
	static class Ans implements Comparable<Ans>{
			int start;
			int cnt;
			public Ans(int start, int cnt){
			this.start = start;
			this.cnt = cnt;
			}
			
			@Override
			public int compareTo(Ans o) {
				if(this.cnt==o.cnt) {
					return this.start - o.start; //오름차순정렬
				}
				return o.cnt- this.cnt; //cnt가 큰순
				//start는 최솟값, cnt는 최댓값이 나와야 하기 떄문이다.
			}
			@Override
			public String toString() {
				return start + " "+ cnt;
			}
		
		}
	static Ans ans;
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input/swea_1861.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <=T ; tc++) {
		
		N=sc.nextInt();
		map = new int[N+2][N+2];//경계선체크안해도됨. 값안넣은곳에는 0. 
		
		for (int i = 1; i <= N; i++) {//대신 1부터넣고 N까지 채우면됨.
			for (int j = 1; j <= N; j++) {
				map[i][j]= sc.nextInt();
			}
		}	
		ans = new Ans(Integer.MAX_VALUE, 0);
				
//		print(map);
		//모든방이 출발점이 될 수 있으므로 2중루프로 시작
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				//사방탐색하여 +1많은 방으로 이동, 더이상 이동할곳없으면 멈춤.
				move(i,j,1,map[i][j]);//1은 몇번이동하냐의 초기값
			}
		}	
			
			
			System.out.printf("#%d %s\n",tc, ans.toString());
		}
		
		
	}

	private static void move(int r, int c, int cnt,int start) {
		//재귀함수가 다 돌앗을 때
		Ans temp = new Ans(start,cnt);
		if(ans.compareTo(temp)>0) {
			ans = temp;
		}
		for (int k = 0; k < dc.length; k++) {
			int nr = r+dr[k];
			int nc = c+dc[k];
			if(map[r][c]==map[nr][nc]-1){
				//경계값 체크는 배열을 +2로만들었기때문에 필요가 없다.
			move(nr,nc,cnt+1,start);//인자로 출발점은 그대로가져감.  
			}
		}
		
	}
	static int[] dr = {-1,1,0,0};
	static int[] dc = {0,0,-1,1};

}

구해야할것: 이동할수있는 방의 개수가 최대인 방이 여럿이라면 그 중에서 적힌 수가 가장 작은것을 출력한다.

 

방 객체가 갖고있는것: 처음에 출발한번호(start), 몇칸 이동했는지(cnt)

재귀함수를 돌며 start와 cnt의 값이 계속 변화하므로 함수의 인자로 준다.

cnt는 +1해서 넘겨줌.