[BaekJoon] 백준 15683번 감시

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

15683번: 감시

 

모든 CCTV의 감시 가능한 모든 방향을 계산해야한다.

각 cctv가 감시할 수 있는 경우의 수를 생각하면서 풀면 쉽다. 

 

1번은 4개

2번은 2개

3번은 4개

4번 4개

5번 1개

 

 

 

 

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

public class Main {
	static class CCTV{
		int i;
		int j;
		int type;
		
		public CCTV(int i, int j, int t) {
			this.i = i; this.j = j; this.type = t;
		}
	}
	static ArrayList<CCTV> cctv;
	static int MIN;
	static int N;
	static int M;
	public static void main(String[] args) {
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			String[] str = br.readLine().split(" ");
			N = Integer.parseInt(str[0]);
			M = Integer.parseInt(str[1]);
			int[][] room = new int[N][M];
			cctv = new ArrayList<>();
			MIN = Integer.MAX_VALUE;
			
			for(int i = 0; i<N; i++) {
				String[] tmp = br.readLine().split(" ");
				for(int j = 0; j<M; j++) {
					room[i][j] = Integer.parseInt(tmp[j]);
					if(room[i][j] > 0 && room[i][j] < 6) {
						cctv.add(new CCTV(i, j, room[i][j]));
					}
				}
			}
			func(0, room);
			System.out.println(MIN);
		}catch(IOException e) {	
		}
	}
	
	public static void func(int index, int[][] room) {
		if(index >= cctv.size()) {
			//TODO: Calculate room
			int count = 0;
			for(int i = 0; i<N;i++) {
				for(int j = 0; j<M; j++) {
					if(room[i][j] == 0)
						count++;
				}
			}
			if(MIN > count) {
				MIN = count;
			}
			return;
		}
		else {
			CCTV cam = cctv.get(index);
			//1번 카메라 
			if(cam.type == 1) {
				int[][] r = deepCopy(room);
				for(int i = cam.i; i>= 0; i--) {
					if(r[i][cam.j] == 6)
						break;
					r[i][cam.j] = 7;
				}
				func(index+1, r);
				
				int[][] r2 = deepCopy(room);
				for(int j = cam.j; j<M; j++) {
					if(r2[cam.i][j] == 6)
						break;
					r2[cam.i][j] = 7;
				}
				func(index+1, r2);
				
				int[][] r3 = deepCopy(room);
				for(int i = cam.i; i<N; i++) {
					if(r3[i][cam.j] == 6)
						break;
					r3[i][cam.j] = 7;
				}
				func(index+1, r3);
				
				int[][] r4 = deepCopy(room);
				for(int j = cam.j; j>=0; j--) {
					if(r4[cam.i][j] == 6)
						break;
					r4[cam.i][j] = 7;
				}
				func(index+1, r4);
			}
			//2번 카메라
			else if(cam.type == 2) {
				int[][] r = deepCopy(room);
				for(int j = cam.j; j>=0; j--) {
					if(r[cam.i][j] == 6)
						break;
					r[cam.i][j] = 7;
				}
				for(int j = cam.j; j<M; j++) {
					if(r[cam.i][j] == 6)
						break;
					r[cam.i][j] = 7;
				}
				func(index+1, r);
				
				int[][] r2 = deepCopy(room);
				for(int i = cam.i; i>=0; i--) {
					if(r2[i][cam.j] == 6)
						break;
					r2[i][cam.j] = 7;
				}
				for(int i = cam.i; i<N; i++) {
					if(r2[i][cam.j] == 6)
						break;
					r2[i][cam.j] = 7;
				}
				func(index+1, r2);
			}
			//3번 카메라
			else if(cam.type == 3) {
				int[][] r = deepCopy(room);
				//오른쪽 공통 
				for(int j = cam.j; j<M; j++) {
					if(r[cam.i][j] == 6)
						break;
					r[cam.i][j] = 7;
				}
				int[][] r_1 = deepCopy(r);
				
				for(int i = cam.i; i>=0; i--) {
					if(r[i][cam.j] == 6)
						break;
					r[i][cam.j] = 7;
				}
				func(index+1, r);
				
				for(int i = cam.i; i<N; i++) {
					if(r_1[i][cam.j] == 6)
						break;
					r_1[i][cam.j] = 7;
				}
				func(index+1, r_1);
				
				//왼쪽 공통
				int[][] r2 = deepCopy(room);
				for(int j = cam.j; j>=0; j--) {
					if(r2[cam.i][j] == 6)
						break;
					r2[cam.i][j] = 7;
				}
				int[][] r2_1 = deepCopy(r2);
				
				for(int i = cam.i; i>=0; i--) {
					if(r2[i][cam.j] == 6)
						break;
					r2[i][cam.j] = 7;
				}
				func(index+1, r2);
				
				for(int i = cam.i; i<N; i++) {
					if(r2_1[i][cam.j] == 6)
						break;
					r2_1[i][cam.j] = 7;
				}
				func(index+1, r2_1);
				
			}
			//4번 카메라
			else if(cam.type == 4) {
				//양옆 감시
				int[][] r = deepCopy(room);
				for(int j = cam.j; j>=0; j--) {
					if(r[cam.i][j] == 6)
						break;
					r[cam.i][j] = 7;
				}
				for(int j = cam.j; j<M; j++) {
					if(r[cam.i][j] == 6)
						break;
					r[cam.i][j] = 7;
				}
				int[][] r_1 = deepCopy(r);
				for(int i = cam.i; i>=0; i--) {
					if(r[i][cam.j] == 6)
						break;
					r[i][cam.j] = 7;
				}
				func(index+1, r);
				
				for(int i = cam.i; i<N; i++) {
					if(r_1[i][cam.j] == 6)
						break;
					r_1[i][cam.j] = 7;
				}
				func(index+1, r_1);
				
				//위아래 감시
				int[][] r2 = deepCopy(room);
				for(int i = cam.i; i>=0; i--) {
					if(r2[i][cam.j] == 6)
						break;
					r2[i][cam.j] = 7;
				}
				for(int i = cam.i; i<N; i++) {
					if(r2[i][cam.j] == 6)
						break;
					r2[i][cam.j] = 7;
				}
				
				int[][] r2_1 = deepCopy(r2);
				for(int j = cam.j; j>=0; j--) {
					if(r2[cam.i][j] == 6)
						break;
					r2[cam.i][j] = 7;
				}
				func(index+1, r2);
				
				for(int j = cam.j; j<M; j++) {
					if(r2_1[cam.i][j] == 6)
						break;
					r2_1[cam.i][j] = 7;
				}
				func(index+1, r2_1);
			}
			//5번 카메라
			else if(cam.type == 5) {
				int[][] r = deepCopy(room);
				for(int i = cam.i; i>=0; i--) {
					if(r[i][cam.j] == 6)
						break;
					r[i][cam.j] = 7;
				}
				for(int i = cam.i; i<N; i++) {
					if(r[i][cam.j] == 6)
						break;
					r[i][cam.j] = 7;
				}
				
				for(int j = cam.j; j>=0; j--) {
					if(r[cam.i][j] == 6)
						break;
					r[cam.i][j] = 7;
				}
				for(int j = cam.j; j<M; j++) {
					if(r[cam.i][j] == 6)
						break;
					r[cam.i][j] = 7;
				}
				
				func(index+1, r);
			}
		}
	}
	
	public static int[][] deepCopy(int[][] target) {
		int[][] result = new int[N][M];
		for(int i = 0; i<N; i++) {
			System.arraycopy(target[i],  0,  result[i],  0,  M);
		}
		
		return result;
	}
	
}