[swexpert] 2105. 디저트 카페 (java, 시뮬레이션, 모든 탐색)

좀 되는 대로 푼 시뮬 문제라서 다른 방법도 공부해야겠다 

import java.util.Scanner;

public class Solution {
	static int t,n;
	static int[][] map;
	static int [] xpos= {1,-1,-1,1};
	static int [] ypos= {1,1,-1,-1};
	static int ans;
	static boolean vis[];
	static boolean vis_dir[];
	static int sy,sx;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		t=sc.nextInt();
		for (int tc = 1; tc <= t; tc++) {
			n=sc.nextInt();
			map=new int[n][n];
			ans=-1;
			for (int i = 0; i <n; i++) {
				for (int j = 0; j < n; j++) {
					map[i][j]=sc.nextInt();
				}
			}
			for (int i = 0; i <n; i++) {
				for (int j = 0; j < n; j++) {
					vis=new boolean[n*n+1];
					vis_dir=new boolean[4];
					vis[map[i][j]]=true;
					sy=i; sx=j;
					go(i,j,map[i][j],0,0);
				}
			}
			System.out.printf("#%d %d\n",tc,ans);
			
		}
	}
	private static void go(int y,int x, int start,int dir,int cnt) {
		if(cnt!=0 && (sy==y && sx==x)) {// 처음 위치로 되돌아오고 cnt가 0이 아닐때
			if(cnt>ans && cnt!=0)ans=cnt;
			return;
		}
		if(dir==4)return;
		int yy=y+ypos[dir];
		int xx=x+xpos[dir];
		if(xx>=0 && xx<n && yy>=0 && yy<n) {
			if(yy==sy && xx==sx) { //시작점 (방문했어도 시작점은 예외처리)
				go(yy,xx,start,dir+1,cnt+1);
			}else if(vis[map[yy][xx]]) {// 시작점이 아니고 방문했던 곳
				//지금 가능 방향에서 방문한 곳이 있다면 다음 방향 탐색 가능.
				//없다면 그냥 끝난다.
				if(vis_dir[dir]) {
					go(y,x,start,dir+1,cnt);
				}
			}else { //갈 수 있다면 같은 방향도 가보고 다른 방향도 가본다.
				// 이 방향으로 가봤다면 다음 방향도 가보기
				if(vis_dir[dir]) {
					go(y,x,start,dir+1,cnt);
				}
				//같은 방향 가기
				vis_dir[dir]=true;
				vis[map[yy][xx]]=true;
				go(yy,xx,start,dir,cnt+1);
				vis_dir[dir]=false;
				vis[map[yy][xx]]=false;
				
			}
		}else if(vis_dir[dir]) {// 범위를 벗어나고 이 방향으로 간 곳이 있다면 다른 방향으로 전환
			go(y,x,start,dir+1,cnt);
		}
		
	}
	
	
	
}