[Java] BOJ15683_감시

www.acmicpc.net/problem/15683

15683번: 감시

---

감시카메라를 방향별로 다 놓아보고 사각지대를 찾아야 하는 브루트 포스 구현 문제이다. 감시 영역이 겹치는 부분에 대한 처리를 하기 위하여 빈칸(값이 0)인 부분을 값 7로 세팅했다.

 

카메라 종류별로 CASE를 나누어 주었고 종류에서 방향별로 반복문을 돌아 부분집합을 구성했다.

어떤 카메라가 특정 방향으로 감시를 할 때 감시가 되는 부분 중 값이 7인 곳은 빈칸이므로 사각지대를 하나 감소시켰고 그 부분의 값을 1 증가시켜 8로 세팅했다.

감시가 되는 부분 중 값이 8 이상인 곳은 이미 감시가 되고있는 곳이므로 사각지대의 수를 감소시키지는 않았지만 추후 감시했던 부분을 되돌리기 위해 값을 1 증가시켜줬다. (값이 9인 곳에서 감시했던 부분을 되돌려 값을 1 감소시켜도 아직 값이 8이므로 감시 중인 부분인 것이다.)

 

감시가 끝나고 되돌릴 때는 del이라는 boolean 변수를 이용하여 감시 부분들의 값을 1 감소시켰다.

 

방향벡터 dr, dc는 반복문의 편의성을 위해 확장시킨것이다.

 

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

	static int N, M;
	static int arr[][];
	static ArrayList<int[]> camera = new ArrayList<>();
	static int res = Integer.MAX_VALUE;
	static int[] dr = { -1, 0, 1, 0, -1, 0 };
	static int[] dc = { 0, 1, 0, -1, 0, 1 };
	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());
		M = Integer.parseInt(st.nextToken());
		int firstsagak = 0;
		arr = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				int temp = Integer.parseInt(st.nextToken());
				arr[i][j] = temp;
				if(temp != 0 && temp != 6) camera.add(new int[] {i, j, temp});
				if(temp == 0) {
					arr[i][j] = 7;
					firstsagak++;
				}
			}
		}
		watch(0, firstsagak);
		System.out.println(res);
	}

	public static void watch(int cnt, int sagak) {
		if(cnt == camera.size()) {
			res = Math.min(res, sagak);
			return;
		}
		
		switch(camera.get(cnt)[2]) {
		case 1:
			for(int i = 0; i < 4; i++) {
				int val = gamsi(1, i, cnt, false);
				watch(cnt+1, sagak - val);
				gamsi(1, i, cnt, true);
			}
			break;
		case 2:
			for(int i = 0; i < 2; i++) {
				int val = gamsi(2, i, cnt, false);
				watch(cnt+1, sagak - val);
				gamsi(2, i, cnt, true);
			}
			break;
		case 3:
			for(int i = 0; i < 4; i++) {
				int val = gamsi(3, i, cnt, false);
				watch(cnt+1, sagak - val);
				gamsi(3, i, cnt, true);
			}
			break;
		case 4:
			for(int i = 0; i < 4; i++) {
				int val = gamsi(4, i, cnt, false);
				watch(cnt+1, sagak - val);
				gamsi(4, i, cnt, true);
			}
			break;
		case 5:
			int val = gamsi(5, -1, cnt, false);
			watch(cnt+1, sagak - val);
			gamsi(5, -1, cnt, true);
			break;
		}
	}
	
	public static int gamsi(int type, int direc, int current, boolean del) {
		int cnt = 0;
		switch(type) {
		case 1: {
			int nr = camera.get(current)[0];
			int nc = camera.get(current)[1];
			while(true) {
				nr += dr[direc];
				nc += dc[direc];
				if(nr < 0 || nc < 0 || nr >= N || nc >= M || arr[nr][nc]==6) break;
				if(arr[nr][nc] == 7 && !del) {
					cnt++;
					arr[nr][nc]++;
				} else if(arr[nr][nc] > 7) {
					if(del) {
						arr[nr][nc]--;
					} else {
						arr[nr][nc]++;
					}
				}
				
			}
		}
			break;
		case 2: {
			for(int i = 0; i < 3; i = i+2) {
				int nr = camera.get(current)[0];
				int nc = camera.get(current)[1];
				while(true) {
					nr += dr[direc+i];
					nc += dc[direc+i];
					if(nr < 0 || nc < 0 || nr >= N || nc >= M || arr[nr][nc]==6) break;
					if(arr[nr][nc] == 7 && !del) {
						cnt++;
						arr[nr][nc]++;
					} else if(arr[nr][nc] > 7) {
						if(del) {
							arr[nr][nc]--;
						} else {
							arr[nr][nc]++;
						}
					}
				}
			}
		}
			break;
		case 3: {
			for(int i = 0; i < 2; i++) {
				int nr = camera.get(current)[0];
				int nc = camera.get(current)[1];
				while(true) {
					nr += dr[direc+i];
					nc += dc[direc+i];
					if(nr < 0 || nc < 0 || nr >= N || nc >= M || arr[nr][nc]==6) break;
					if(arr[nr][nc] == 7 && !del) {
						cnt++;
						arr[nr][nc]++;
					} else if(arr[nr][nc] > 7) {
						if(del) {
							arr[nr][nc]--;
						} else {
							arr[nr][nc]++;
						}
					}
				}
			}
		}
			break;
		case 4: {
			for(int i = 0; i < 3; i++) {
				int nr = camera.get(current)[0];
				int nc = camera.get(current)[1];
				while(true) {
					nr += dr[direc+i];
					nc += dc[direc+i];
					if(nr < 0 || nc < 0 || nr >= N || nc >= M || arr[nr][nc]==6) break;
					if(arr[nr][nc] == 7 && !del) {
						cnt++;
						arr[nr][nc]++;
					} else if(arr[nr][nc] > 7) {
						if(del) {
							arr[nr][nc]--;
						} else {
							arr[nr][nc]++;
						}
					}
				}
			}
		}
			break;
		case 5: {
			for(int i = 0; i < 4; i++) {
				int nr = camera.get(current)[0];
				int nc = camera.get(current)[1];
				while(true) {
					nr += dr[i];
					nc += dc[i];
					if(nr < 0 || nc < 0 || nr >= N || nc >= M || arr[nr][nc]==6) break;
					if(arr[nr][nc] == 7 && !del) {
						cnt++;
						arr[nr][nc]++;
					} else if(arr[nr][nc] > 7) {
						if(del) {
							arr[nr][nc]--;
						} else {
							arr[nr][nc]++;
						}
					}
				}
			}
		}
			break;
		}
		
		return cnt;
	}
}