[Java] 백준15683 - 감시

https://www.acmicpc.net/problem/15683

15683번: 감시

 

다섯 종류의 CCTV가 있고 모두 각도를 조절할 수 있다.

사각지대를 최소화할 수 있는 경우의 수를 구하는 것이다.

 

모든 경우를 찾기 위해 DFS로 탐색했다.

1,2,3,4,5번이 각각 탐색 방향이 다른데, 

한 방향으로 탐색하는 메소드를 구현해서 방향에 맞게 돌려주고, 수에 맞게 호출해줬다.

 

package BOJ_SS;

import java.util.*;

public class boj15683 {
	public static int n, m, min, cnt=0;
	public static int[] dirs = {0,1,2,3,4,1,2}; //상우하좌
	public static int[][] map;
	public static ArrayList<int[]> cctv = new ArrayList<>();
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		// 0 빈칸 
		// 6 벽
		// 1~5 CCTV 번호 위치
		
		n = sc.nextInt();
		m = sc.nextInt();
		map = new int[n][m];
		min = n * m;
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				int num = sc.nextInt();
				if(num == 6) {
					map[i][j]=6;
				}else if(num!=0) {
					cctv.add(new int[] {i,j,num,0});
					cnt++;
				}
			}
		}		
		
		dfs(0);
		System.out.println(min);
	}
	
	public static void dfs(int depth) {
		if(depth == cnt) {
			int blind = cntBlind();
			if(blind < min) {
//				System.out.println("==========");
//				showMap();
//				System.out.println("방향==>"+cctv.get(1)[3]);
				min = blind;
			}
			resetMap();
			return ;
		}
		
		int[] cctvDetail = cctv.get(depth);
		int cctvNum = cctvDetail[2]; 
		
		if(cctvNum==6)
			dfs(depth+1);
		else if(cctvNum==2) {
			cctvDetail[3] = 1;
			dfs(depth+1);
			cctvDetail[3] = 2;
			dfs(depth+1);
		}else {
			for(int i=1; i<=4; i++) {
				cctvDetail[3] = i;
				dfs(depth+1);
			}
		}
	}
	
	public static int cntBlind() {
		int visible = 0;
		for(int i=0; i<cnt; i++) {
			int[] cctvDetail = cctv.get(i);
			int x = cctvDetail[0];
			int y = cctvDetail[1];
			int num = cctvDetail[2];
			int dir = cctvDetail[3];
			
			switch(num) {
			case 1:{
				makeRoad(x,y,dir);
				break;
			}
			case 2:{
				makeRoad(x,y,dir);
				makeRoad(x,y,dir+2);
				break;
			}
			case 3:{
				makeRoad(x,y,dir);
				makeRoad(x,y,dirs[dir+1]);
				break;
			}
			case 4:{
				makeRoad(x,y,dir);
				makeRoad(x,y,dirs[dir+1]);
				makeRoad(x,y,dirs[dir+2]);
				break;
			}
			case 5:{
				makeRoad(x,y,1);
				makeRoad(x,y,2);
				makeRoad(x,y,3);
				makeRoad(x,y,4);
			}
			}
			
		}
		
		for(int i=0; i<n; i++)
			for(int j=0; j<m; j++)
				if(map[i][j]!=0)
					visible++;
		
		
		
		return n*m - visible;
	}
	
	public static void makeRoad(int x, int y, int dir) {
		switch(dir) {
		case 1:{ // 상
			for(int i=x; i>=0; i--){
				if(map[i][y]==6)
					break;
				map[i][y] = -1;
			}
			break;
		}
		case 2:{  // 우 
			for(int i=y; i<m; i++) {
				if(map[x][i]==6)
					break;
				map[x][i] = -1;
			}
			break;
		}
		case 3:{  // 하
			for(int i=x; i<n; i++) {
				if(map[i][y]==6)
					break;
				map[i][y] = -1;
			}
			break;
		}default:{  // 좌
			for(int i=y; i>=0; i--) {
				if(map[x][i]==6)
					break;
				map[x][i] = -1;
			}
			break;
		}
		}
	}
	
	public static void resetMap() {
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++)
				if(map[i][j]!=6)
					map[i][j]=0;
		}
	}
	
	public static void showMap() {
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(map[i][j]==-1)
					System.out.print("# ");
				else
					System.out.print(map[i][j]+" ");
			}
			System.out.println();
		}
	}
}