[BOJ] 감시

❗ 풀이 과정

• cctv의 종류마다 고려해야하는 경우가 다르다.
  • type1 : ⬆/➡/⬇/⬅/ 4가지
  • type2 : ⬅➡/⬆⬇ 2가지
  • type3 : ⬆➡/➡⬇/⬇⬅/⬅⬆ 4가지
  • type4 : ⬅⬆➡/⬆➡⬇/➡⬇⬅/⬇⬅⬆ 4가지
• 깊은 복사를 해줘야한다.
• 반복적인 동작은 method로 선언해줬다. ( 빈공간을 구하는 함수isEmpty, 색칠하기 colorMap)
• DFS 함수에서 cctv 타입별로 탐방을 한다.

🤜 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main_15683_감시 {
	//static int [][] map ;
	static int N,M;
	static int [][] cctvPos = new int [9][3];
	static int min_result;
	static int [] dx = {0,1,0,-1};
	static int [] dy = {-1,0,1,0};
	
	// 빈공간을 구하는 함수
	static int getEmpty(int [][] tmp_map) {
		int cnt=0;
		for(int n=0;n<N;n++) {
			for(int m=0;m<M;m++) {
				if(tmp_map[n][m]==0) cnt++;
				//System.out.print(tmp_map[n][m]+" ");
			}
			//System.out.println();
		}
		//System.out.println();
		return cnt;
	}
	
	static void colorMap(int x,int y,int [][] tmp_map,int i) {
 		while(true) {
 			if(x+dx[i]<0 || x+dx[i]>=M || y+dy[i]<0 || y+dy[i]>=N) break;
 			x+=dx[i];
 			y+=dy[i];
 			if(tmp_map[y][x]==6) break;
 			tmp_map[y][x]=-1;
 		}

	}
	
	static void DFS(int start,int Cnt,int [][] sub_map) {
		// 다 탐방했으니 끝!
		if(start==Cnt) {min_result=Math.min(getEmpty(sub_map),min_result); return;}

		// 방향별로 ### 찍어주기
		int x = cctvPos[start][0]; 
		int y = cctvPos[start][1];

		
		switch(cctvPos[start][2]) {
		case 1:
			 	for(int i=0;i<4;i++) {
			 		//   map 복사
			 		int [][] tmp_map = new int [N][M];
			 		for(int n=0;n<N;n++) {
			 			for(int m=0;m<M;m++) {
			 				tmp_map[n][m]=sub_map[n][m];
			 			}
			 		}
			 		colorMap(x,y,tmp_map,i);
			 		
			 		DFS(start+1,Cnt,tmp_map);
			 		////////////////////////
			 	}
			 	
			 	break;
		case 2:
				for(int i=0;i<2;i++) {
					// map 복사
			 		int [][] tmp_map = new int [N][M];
			 		for(int n=0;n<N;n++) {
			 			for(int m=0;m<M;m++) {
			 				tmp_map[n][m]=sub_map[n][m];
			 			}
			 		}
			 		colorMap(x,y,tmp_map,i);
			 		colorMap(x,y,tmp_map,i+2);
			 		
			 		DFS(start+1,Cnt,tmp_map);
			 		/////////////////////
				}
				break;
		case 3:
				for(int i=0;i<4;i++) {
					// map 복사
			 		int [][] tmp_map = new int [N][M];
			 		for(int n=0;n<N;n++) {
			 			for(int m=0;m<M;m++) {
			 				tmp_map[n][m]=sub_map[n][m];
			 			}
			 		}
					colorMap(x,y,tmp_map,i);
					colorMap(x,y,tmp_map,(i+1)%4);
					
					DFS(start+1,Cnt,tmp_map);
			 		/////////////////////////
				}
				break;
		case 4:
				for(int i=0;i<4;i++) {
					// map 복사
			 		int [][] tmp_map = new int [N][M];
			 		for(int n=0;n<N;n++) {
			 			for(int m=0;m<M;m++) {
			 				tmp_map[n][m]=sub_map[n][m];
			 			}
			 		}
			 		
			 		for(int j=0;j<4;j++) {
						if(i!=j) colorMap(x,y,tmp_map,j);
					}

					DFS(start+1,Cnt,tmp_map);
			 		///////////////////////////////
					
				}
				break;
		case 5:
				// only one

				colorMap(x,y,sub_map,0);
				colorMap(x,y,sub_map,1);
				colorMap(x,y,sub_map,2);
				colorMap(x,y,sub_map,3);
				
		 		DFS(start+1,Cnt,sub_map);
		 		//////////////////////////////////////////
				break;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader 	br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());	//  N : 세로
		M = Integer.parseInt(st.nextToken());	//  M : 가로
		int [][] map = new int [N][M];						// map
		int cctvCnt = 0;
		// map 정보 받기
		for(int n=0;n<N;n++) {
			st = new StringTokenizer(br.readLine());
			for(int m=0;m<M;m++) {
				map[n][m]=Integer.parseInt(st.nextToken());	
				if(map[n][m]!=0 && map[n][m]!=6) {
					cctvPos[cctvCnt][0] = m;	// X
					cctvPos[cctvCnt][1] = n;	// Y
					cctvPos[cctvCnt][2] = map[n][m];	// cctv_type
					cctvCnt++;
				}
			}
		}
		min_result=M*N;
		DFS(0,cctvCnt,map);
		System.out.println(min_result);
		
	}
}