[SWExpertAcademy] 1861. 정사각형 방

문제

풀이

DFS
1. 이차원 배열의 첫 인덱스부터 시작해서 이동할 수 있을 때까지 dfs 실행
2. dfs과정 중 방문하게 된 인덱스에 현재 depth와 start위치 저장
-> 이를 통해 방문했던 인덱스를 다시 방문하지 않도록 함
3. 모든 인덱스에 depth와 start위치가 저장될 때까지 1~2과정 반복
4. 최대 depth와 그 시작 위치 print

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.Stack;

public class Solution {
	
	static int N;
	//입력받은 배열
	static int[][]arr;
	//최대 depth, start지점
	static int[][][]memo;
	static int[] answer;

	static void search() {
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if(memo[i][j][1]==0) {
					memo[i][j][1]=arr[i][j];
					memo[i][j][0]=dfs(i,j,1,arr[i][j]);
				}
			}
		}
	}

	static int dfs(int x, int y,int depth, int start) {
		int[] dx = {1,-1,0,0};
		int[] dy = {0,0,1,-1};
		
		for(int k=0;k<4;k++) {
			int nx=x+dx[k];
			int ny=y+dy[k];
			if(nx>=0&&nx<N&&ny>=0&&ny<N&&arr[nx][ny]-arr[x][y]==1) {
				memo[nx][ny][0]=depth;
				memo[nx][ny][1]=start;
				return dfs(nx,ny,depth+1,start);
			}
		}
		//MAX depth 체크
		if(answer[0]<=depth) {
			if(answer[0]==depth&&answer[1]>memo[x][y][1]) {
				answer[1]=memo[x][y][1];
			}
			else if(answer[0]<depth){
				answer[0]=depth;
				answer[1]=memo[x][y][1];
			}
		}
		return depth;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		
		for(int test_case = 1; test_case <= T; test_case++){
			
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			arr = new int[N][N];
			memo = new int[N][N][2];
			answer= new int[2];
			answer[0]=0;
			answer[1]=0;
			for(int i=0;i<N;i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0;j<N;j++) 
					arr[i][j]=Integer.parseInt(st.nextToken());
			}
			search();
			sb.append("#"+test_case+" "+answer[1]+" "+answer[0]+"\n");
		}
		bw.write(sb.toString());
		bw.flush();
	}
}