[15683] 감시

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

15683번: 감시

---

import java.util.Scanner;
import java.util.ArrayList;

class Main {

	static int N, M, L, answer = 99999999;
	static int[][] arr, map;
	static ArrayList<CCTV> list = new ArrayList<CCTV>();
	static int[] before, after, temp;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		arr = new int[N][M];
		map = new int[N][M];
		before = new int[6];
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				arr[i][j] = sc.nextInt();
				if(arr[i][j] == 1) list.add(new CCTV(i, j, 1));
				if(arr[i][j] == 2) list.add(new CCTV(i, j, 2));
				if(arr[i][j] == 3) list.add(new CCTV(i, j, 3));
				if(arr[i][j] == 4) list.add(new CCTV(i, j, 4));
				if(arr[i][j] == 5) list.add(new CCTV(i, j, 5));
			}
		}
		
		L = list.size();
		temp = new int[L];
		copy();
		if(L==0) {
			System.out.println(calc());
			return;
		}
		
		for(int i=0; i<4; i++) {
			temp[0] = i+1;
			combination(i, 0);
		}
		
		combination(0, 0);
		
		System.out.println(answer);
		
	}
	
	public static void combination(int start, int depth) {
		if(depth == L-1) {
			copy();
			for(int i=0; i<L; i++) {
				CCTV c = list.get(i);
				spread(c.x, c.y, c.type, temp[i]);
			}
		
			answer = Math.min(calc(), answer);
			
			return;
		} 
		for(int i=start; i<4; i++) {
			temp[depth+1] = i+1;
			combination(i, depth+1);
		}
	}
	
	public static int calc() {
		int sum = 0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j] == 0) sum++;
			}
		}
		return sum;
	}
	
	public static void spread(int x, int y, int type, int dir) {
		
		if(type == 1) {
			if(dir == 1) DFS(x, y, type, 1);
			if(dir == 2) DFS(x, y, type, 2);
			if(dir == 3) DFS(x, y, type, 3);
			if(dir == 4) DFS(x, y, type, 4);
		} else if(type == 2) {
			if(dir == 1) {
				DFS(x, y, type, 1);
				DFS(x, y, type, 2);
			}
			if(dir == 2) {
				DFS(x, y, type, 3);
				DFS(x, y, type, 4);
			}
			if(dir == 3) {
				DFS(x, y, type, 1);
				DFS(x, y, type, 2);
			}
			if(dir == 4) {
				DFS(x, y, type, 3);
				DFS(x, y, type, 4);
			}
			
		} else if(type == 3) {
			if(dir == 1) {
				DFS(x, y, type, 1);
				DFS(x, y, type, 4);
			}
			if(dir == 2) {
				DFS(x, y, type, 2);
				DFS(x, y, type, 4);
			}
			if(dir == 3) {
				DFS(x, y, type, 2);
				DFS(x, y, type, 3);
			}
			if(dir == 4) {
				DFS(x, y, type, 1);
				DFS(x, y, type, 3);
			}
		} else if(type == 4) {
			if(dir == 1) {
				DFS(x, y, type, 1);
				DFS(x, y, type, 2);
				DFS(x, y, type, 4);
			}
			if(dir == 2) {
				DFS(x, y, type, 2);
				DFS(x, y, type, 3);
				DFS(x, y, type, 4);
			}
			if(dir == 3) {
				DFS(x, y, type, 1);
				DFS(x, y, type, 2);
				DFS(x, y, type, 3);
			}
			if(dir == 4) {
				DFS(x, y, type, 1);
				DFS(x, y, type, 3);
				DFS(x, y, type, 4);
			}
		} else if(type == 5) {
			DFS(x, y, type, 1);
			DFS(x, y, type, 2);
			DFS(x, y, type, 3);
			DFS(x, y, type, 4);
		}
	}
			
	
	public static void DFS(int x, int y, int type, int dir) {
		
		int nx = x;
		int ny = y;
		
		if(dir == 1) {
			// 동	
			nx = x;
			ny = y+1;
		} else if(dir == 2) {
			// 서
			nx = x;
			ny = y-1;
			
		} else if(dir == 3) {
			// 남
			nx = x+1;
			ny = y;
			
		} else if(dir == 4) {
			// 북
			nx = x-1;
			ny = y;
		}
		
		if(!isInside(nx, ny)) return;
		if(map[nx][ny] == 6) return;
		if(map[nx][ny] == 0) map[nx][ny] = type;
		DFS(nx, ny, type, dir);
		
	}

	public static void copy() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				map[i][j] = arr[i][j];
			}
		}
	}

	public static boolean isInside(int x, int y) {
		if (x >= 0 && x < N && y >= 0 && y < M)
			return true;
		else
			return false;
	}
}

class CCTV {
	int x;
	int y;
	int type;

	CCTV(int x, int y, int type) {
		this.x = x;
		this.y = y;
		this.type = type;
	}
}

---

CCTV 를 90도씩 회전시켜서 사각지대의 최소크기를 구하는 브루트포스 문제입니다. 이 문제에서 핵심은 각 CCTV 마다  회전방향을 모두 탐색해야 합니다. 그래서 만약에 CCTV 개수가 3개 이고, 동서남북의 방향을 차례대로 1,2,3,4라고 가정한다면 111, 112, 113, 114, 121, 122, 123, 124 ... 444 까지 모든 조합의 수를 뽑아서 CCTV 마다 회전시켜서 사각지대를 계산하는 방법으로 해결했습니다.

[ 문제 풀이 ]

1. CCTV 의 번호는 1부터 5까지 있기 때문에 CCTV 클래스를 만들어서 좌표 두개와 CCTV 의 type 을 저장했습니다.

2. temp 배열은 CCTV의 개수만큼 길이로 정하여 CCTV 가 돌아갈 모든 방향의 번호를 저장할 배열입니다. 동서남북 순서로 1,2,3,4 를 저장합니다.

3. combination 함수로 모든 조합의 CCTV 방향을 정해주고 spread 함수를 통해서 CCTV가 회전하여 감시할 범위를 map에 표시해줍니다. 이 때 주의할점은 copy() 함수를 이용해서 계산하기 전에 매번 처음에 입력받았던 2차원 배열을 복사해줘야 한다는 점입니다.

4. spread() 를 할 때에는 CCTV가 있는 두개의 좌표와 CCTV 의 type, CCTV 가 돌아갈 방향을 입력받아서 DFS로 CCTV가 감시할 범위를 지도에 표시해줍니다.

5. 지도에 CCTV가 감시할 방향을 표시해줄 때 마다 calc() 함수를 이용하여 사각지대의 크기를 계산하고 최솟값을 answer에 저장해줍니다.