[백준] 15683 : 감시 - JAVA(자바) - 사좋배 공유

 

 

import java.util.ArrayList;
import java.util.Scanner;
class node{
	int x;
	int y;
	int number;
	node(int x, int y, int number){
		this.x=x;
		this.y=y;
		this.number=number;
	}
}
public class Main {
	static int [][]arr;
	static int [][]temparr;
	static ArrayListlist;
	static ArrayListlist2;
	static int cnt;
	static int N;
	static int M;
	static int MIN;
	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		N= sc.nextInt();
		M=sc.nextInt();
		cnt=0;
		arr=new int[N][M];
		list=new ArrayList();
		list2=new ArrayList();
		MIN=Integer.MAX_VALUE;
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				arr[i][j]=sc.nextInt();
				if(arr[i][j]!=0&&arr[i][j]!=6) {
					list2.add(new node(i,j,arr[i][j]));
					cnt++;
				}
			}
		}
		dfs();
		System.out.println(MIN);
	}
	private static void dfs() {
		if(list.size()==cnt) {
			solve();
			return;
		}
		
		for(int i=1;i<=4;i++) {
			list.add(i);
			dfs();
			list.remove(list.size()-1);
		}
	}
	private static void solve() {
		int index=0;
		temparr = new int[N][M];
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				temparr[i][j]=arr[i][j];
			}
		}
		while(index<cnt) {
			node temp = list2.get(index);
			int dir = list.get(index);
			index++;
			pricture(temp,dir);
		}
		int count=0;
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				//System.out.print(temparr[i][j]+" ");
				if(temparr[i][j]==0) {
					count++;
				}
			}
		}
		if(count<MIN) {
			MIN=count;
		}
		
	}
	private static void pricture(node temp, int dir) {
		int number= temp.number;
		int x= temp.x;
		int y= temp.y;
		if(number==1) {
			//오른쪽으로
			if(dir==1) {
				right(x,y);
			}
			//아래로
			else if(dir==2) {
				down(x,y);
			}
			//왼쪽으로
			else if(dir==3) {
				left(x,y);
			}
			//위로
			else if(dir==4) {
				up(x,y);
			}
		}else if(number==2) {
			//양옆으로
			if(dir%2==0) {
				//오른쪽으로
				right(x,y);
				//왼쪽으로
				left(x,y);
			}else if(dir%2==1) {
				//위로
				up(x,y);
				//아래로
				down(x,y);
				
			}
			
		}else if(number==3) {
			if(dir==1) {
				//위로
				up(x,y);
				//오른쪽
				right(x,y);
			}else if(dir==2) {
				//오른쪽
				right(x,y);
				//아래로
				down(x,y);
			}else if(dir==3) {
				//아래로
				down(x,y);
				//왼쪽으로
				left(x,y);
			}else if(dir==4) {
				//왼쪽으로
				left(x,y);
				//위로
				up(x,y);
			}
		}else if(number==4) {
			if(dir==1) {
				up(x,y);
				left(x,y);
				right(x,y);
			}else if(dir==2) {
				up(x,y);
				down(x,y);
				right(x,y);
			}else if(dir==3) {
				down(x,y);
				left(x,y);
				right(x,y);
			}else if(dir==4) {
				up(x,y);
				down(x,y);
				left(x,y);
			}
			
		}else if(number==5) {
			up(x,y);
			down(x,y);
			left(x,y);
			right(x,y);
		}
	}
	private static void up(int x, int y) {
		for(int i=x;i>=0;i--) {
			if(temparr[i][y]==0) {
				temparr[i][y]=-1;
			}else if(temparr[i][y]==6) {
				break;
			}
		}
	}
	private static void left(int x, int y) {
		for(int i=y+1;i<M;i++) {
			if(temparr[x][i]==0) {
				temparr[x][i]=-1;
			}else if(temparr[x][i]==6) {
				break;
			}
		}
	}
	private static void down(int x, int y) {
		for(int i=x;i<N;i++) {
			if(temparr[i][y]==0) {
				temparr[i][y]=-1;
			}else if(temparr[i][y]==6) {
				break;
			}
		}
	}
	private static void right(int x, int y) {
		for(int i=y;i>=0;i--) {
			if(temparr[x][i]==0) {
				temparr[x][i]=-1;
			}
			else if(temparr[x][i]==6) {
				break;
			}
		}
	}
}