[swexpert] 프로세서 연결하기 (java, dfs, 백트래킹)

 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Solution {
	static int t,n;
	static int[][] map;
	static List<int[]> core;
	static boolean[][] vis;
	static int[] xpos= {1,-1,0,0};
	static int[] ypos= {0,0,1,-1};
	static int res;
	static int max_connect;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		t=sc.nextInt();
		for (int tc = 1; tc <=t; tc++) {
			res=Integer.MIN_VALUE;
			n=sc.nextInt();
			map=new int[n][n];
			core=new ArrayList<int[]>();
			max_connect=Integer.MAX_VALUE;
			vis=new boolean[n][n];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					map[i][j]=sc.nextInt();
					if(map[i][j]==1 && (i!=0 && j!=0 && i!=n-1 && j!=n-1)) {
						core.add(new int[] {i,j});
					}
				}
			}
			for(int k=0;k<4;k++) {
				check(core.get(0)[0],core.get(0)[1],k,0,0,0);
			}
			
			System.out.printf("#%d %d\n",tc,max_connect);
			
		}
		
	}
	private static void check(int y, int x,int dir,int start,int cnt,int core_cnt) {
		// 연결된 코어 개수 비교 크거나 같을 때

		if(y==0 || y==n-1 || x==0 || x==n-1) { //전선 연결 끝
			if(start+1==core.size()) {
				if(core_cnt>=res) {
				if(core_cnt>res) {
					res=core_cnt;
					max_connect=cnt;
				}
				else if(max_connect>cnt) {
					max_connect=cnt;
				}
				return;
				}
			}else {
				int ty=core.get(start+1)[0];
				int tx=core.get(start+1)[1];
				for(int k=0;k<4;k++) {
					check(ty,tx,k,start+1,cnt,core_cnt+1);
				}
			}
		
			return;
		}
		
			int yy=y+ypos[dir];
			int xx=x+xpos[dir];
//			현재 이 방향의 코어는 연결 불가할 때
			if(vis[yy][xx] || map[yy][xx]==1) {
				if(start+1==core.size())return;
				int ty=core.get(start+1)[0];
				int tx=core.get(start+1)[1];
				for(int k=0;k<4;k++) {
					check(ty,tx,k,start+1,cnt,core_cnt);
				}
				return;
			}
			vis[yy][xx]=true;
			check(yy,xx,dir,start,cnt+1,core_cnt);
			vis[yy][xx]=false;
	}
	}