SWEA - 프로세서 연결하기 JAVA

package a0404;

import java.util.*;
import java.io.*;

/*
 우선순위 -> 1) 연결 많이 2)선 짧게 
 
 1) 연결해야되는 곳의 위치를 리스트에 담는다 
 2) 리스트에 있는 좌표를 돌면서 중복순열을 돈다(연결가능한곳만) 
 3) 중복순열은 사방탐색으로 일직선 쭉 이을수 있으면 그방향으로 선 놓기 
 4) 리스트 사이즈만큼 탐색했을때 우선순위대로 max값 계산 
 
 
 */
public class 프로세서_연결하기 {

	static int size;
	static int[][] arr;
	static int[][] cannot;
	static ArrayList<int[]> list;		//전선 이어야될 리스트
	
	
	
	static int[] di = {-1, 0, 1, 0};
	static int[] dj = {0, 1, 0, -1};
	
	static boolean check(int i, int j, int dir) {	//해당 방향으로 전선 이을수있는지 체크
		int nowi = i;	int nowj = j;
		int ni = nowi+di[dir];
		int nj = nowj+dj[dir];
		
		while(true) {
			if(ni<0||nj<0||ni>=size||nj>=size)break;
			if(arr[ni][nj]!=0)return false;
			nowi = ni;
			nowj = nj;
			ni = nowi+di[dir];
			nj = nowj+dj[dir];
		}
		return true;
	}
	
	static void getline(int i, int j, int dir) {	//해당방향 전선 연결
		
		int nowi = i;	int nowj = j;
		int ni = nowi+di[dir];
		int nj = nowj+dj[dir];
		
		while(true) {
			if(ni<0||nj<0||ni>=size||nj>=size)break;
			nowi = ni;
			nowj = nj;
			arr[nowi][nowj] = -1;
			ni = nowi+di[dir];
			nj = nowj+dj[dir];
		}	
	}
	
	static void removeline(int i, int j, int dir) {		//다시 전선 없애기  
		
		int nowi = i;	int nowj = j;
		int ni = nowi+di[dir];
		int nj = nowj+dj[dir];
		
		while(true) {
			if(ni<0||nj<0||ni>=size||nj>=size)break;
			nowi = ni;
			nowj = nj;
			arr[nowi][nowj] = 0;
			ni = nowi+di[dir];
			nj = nowj+dj[dir];
		}	
	}
	
	static int first = 0;
	static int maxcnt = 0;
	static int minlen;
	
	static int checklen() {
		int cnt = 0;
		for(int i=0; i<size; i++) {
			for(int j=0; j<size; j++) {
				if(arr[i][j]==-1)cnt++;
			}
		}
		return cnt;
	}
	
	static void permutation(int cnt, int sum) {
		
		//print();
		
		if(cnt == list.size()) {
			if(sum>maxcnt) {			// 더많이 연결했다면 무조건 최소값 바꿈
				maxcnt = sum;
				minlen = checklen();
			}else if(sum==maxcnt) {		// 같은 값이라면 최소값으로 정함 
				minlen = Math.min(minlen, checklen());
			}
			return;
		}
		
		int[] now = list.get(cnt);
		int nowi = now[0];	int nowj = now[1];
		//System.out.println(nowi+" "+nowj);
		for(int d=0; d<4; d++) {
			if(check(nowi, nowj, d)) {
				getline(nowi, nowj, d);
				permutation(cnt+1, sum+1);
				removeline(nowi, nowj, d);
			}else permutation(cnt+1, sum);
		}
	}
	
	static void print() {
		for(int i=0; i<size; i++) {
			for(int j=0; j<size; j++) {
				System.out.print(arr[i][j]+" ");
			}
			System.out.println();
		}
		System.out.println();
	}
	
	public static void main(String[] args) throws Exception{
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int tc = Integer.parseInt(br.readLine());
		
		for(int t=1; t<=tc; t++) {
			
			size = Integer.parseInt(br.readLine());
			arr = new int[size][size];					//입력배열
			//cannot = new int[size][size];
			
			minlen = Integer.MAX_VALUE;
			first = 0;
			maxcnt = 0;
			list = new ArrayList<>();
			
			for(int i=0; i<size; i++) {						//입력 
				StringTokenizer ST = new StringTokenizer(br.readLine());
				for(int j=0; j<size; j++) {
					arr[i][j] = Integer.parseInt(ST.nextToken());
					if(arr[i][j]==1) {
						if(i==0 || j==0 || i==size-1 || j==size-1)first++;
						else list.add(new int[] {i,j});
					}
				}
			}
			
			permutation(0, 0);
			
			System.out.println("#"+t+" "+minlen);
		}
	}
}