[삼성기출]백준15683 - 감시

package sw;

import java.io.*;
import java.util.*;
public class Main15683_감시 {
	
	static int N,M;
	static int[][] map;
	static List<Pos> list;
	static int[][] visit;
	static int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};
	static int[][][] cam = {{}, 		// 카메라 방향설정
			{{0},{1},{2},{3}},
			{{0,2},{1,3}},
			{{0,1},{1,2},{2,3},{3,0}},
			{{0,1,2},{1,2,3},{2,3,0},{3,0,1}},
			{{0,1,2,3}}
	};
	static boolean check(int x, int y) {
		if(x>=0 && x<map.length && y>=0 && y<map[x].length)
			return true;
		else return false;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] input = br.readLine().trim().split(" ");
		N = Integer.parseInt(input[0]);
		M = Integer.parseInt(input[1]);
		map = new int[N][M];
		visit = new int[N][M];		// 각 카메라가 볼수있는 위치 카운트
		list = new ArrayList<>(); 	// 카메라 리스트화 
		int wall = 0;
		for(int i=0; i<N; i++) {
			input = br.readLine().trim().split(" ");
			for(int j=0; j<M; j++) {
				map[i][j] = Integer.parseInt(input[j]);
				if(map[i][j] != 0 && map[i][j] != 6) list.add(new Pos(i,j,map[i][j]));
				else if(map[i][j] == 6) wall ++;
			}
		}
		dfs(0);
		System.out.println(min - wall);	// 카메라가 볼수없는 위치의 개수 - 벽의 갯수
		
	}
	static int dx,dy,ix,iy, min = Integer.MAX_VALUE;
	static void dfs(int depth) {
		if(depth == list.size()) {		// dfs
			int cantSee = 0;			// 모든 카메라 위치 설정하고 볼수없는 위치의 갯수 
			for(int i=0; i<N; i++) {
				for(int j=0; j<M; j++) {
					if(visit[i][j]==0) cantSee++;
				}
			}
			if(cantSee < min) min = cantSee;
			return;
		}
		Pos p = list.get(depth);		// 선택된 카메라
		for(int i=0; i<cam[p.n].length; i++) {	
			List<Pos> stateList = new LinkedList<>();	// 이전상태로 보존해주기 위해 설정. 
			stateList.add(new Pos(p.x,p.y,0));
			visit[p.x][p.y]++;
			for(int j=0; j<cam[p.n][i].length; j++) {
				ix = dir[cam[p.n][i][j]][0];
				iy = dir[cam[p.n][i][j]][1];
				dx = p.x + ix;
				dy = p.y + iy;
				while(check(dx,dy) && map[dx][dy] != 6) {
					if(map[dx][dy] == 0) {
						stateList.add(new Pos(dx,dy,0));
						visit[dx][dy]++;
					}
					dx+=ix;
					dy+=iy;
				}
			}
			dfs(depth+1);		
			while(!stateList.isEmpty()) {		// 이전상태로 보존
				Pos rp = stateList.remove(0);
				visit[rp.x][rp.y]--; 
			}
		}
	}

	static class Pos{
		int x,y,n;

		public Pos(int x, int y, int n) {
			this.x = x;
			this.y = y;
			this.n = n;
		}

		@Override
		public String toString() {
			return "[" + x + "," + y + "," + n + "]";
		}
		
	}
}