[백준] JAVA - 15683. 감시

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

15683번: 감시

생각

'SWEA 1767. 프로세서 연결하기'와 로직이 비슷하다고 생각했습니다. CCTV가 탐색할수있는 영역을 모두 탐색하여 CCTV를 켜준 곳을 9로 마스킹처리를 해줬습니다. 그 다음 CCTV를 다시 0 값을 넣어 꺼줬다고 생각했는데 CCTV가 탐색하는 영역이 겹칠 수 있기 때문에 이렇게 바로 값을 특정 값으로 업데이트 시켜줘서 계속 틀렸습니다ㅠㅡㅠ 

 

1. 비트 마스킹으로 CCTV의 방향 조합을 만들어줬습니다. (위 : 0001 , 오른쪽 : 0010 ,아래 : 0100 , 왼쪽 : 1000) 이렇게 방향 비트를 설정한다음 OR 연산을 통해 각 CCTV의 방향 조합을 1차원 배열로 나타낼 수 있습니다.

2. CCTV가 탐색할 수 있는 모든 경우를 확인하는 함수를 DFS로 구현했습니다. CCTV의 모든 방향을 탐색할때 특정 값으로 바로 마스킹 처리를 해주지 않고 copymap에 더하기 연산과 빼기 연산을 통해 CCTV의 탐색 영역을 마스킹처리 했습니다.

3. 이때 CCTV는 범위를 벗어나거나 벽을 만났을때만 탐색이 불가능합니다.

4. CCTV의 개수만큼 탐색을 완료했다면 사각지대 영역을 체크하는 check() 함수를 통해 영역의 크기를 카운트합니다.

5. 사각지대의 최소값을 찾아 출력합니다.

 

Java Code

package com.java.algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ_15683_감시 {
	static int R,C;
	static int[][] map;
	static int[][] copymap;
	static int ans;
	static int[] dy = {1,0,-1,0};
	static int[] dx = {0,1,0,-1};
	static int up = 1, right = 2, down = 4, left = 8;
	static int[][] dirs = {
			{},
			{up, right, down, left}, // 1번
			{up|down, right|left}, // 2번
			{up|right, right|down, down|left, left|up}, // 3번
			{left|up|right, up|right|down, left|down|right, up|left|down}, //4번
			{up|right|down|left} // 5번
	};
	
	static List<CCTV> cctvs;
	
	static class CCTV{
		int y,x,num;
		
		public CCTV(int y, int x, int num) {
			super();
			this.y = y;
			this.x = x;
			this.num = num;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		map = new int[R][C];
		copymap = new int[R][C];
		cctvs = new ArrayList<>();
		ans = Integer.MAX_VALUE;
		
		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < C; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] != 0 && map[i][j] != 6) {
					cctvs.add(new CCTV(i, j, map[i][j]));
				}
			}
		}
		copyMap();
		rotate(0);
		System.out.println(ans);
	}
	
	//cctv 90도 회전시켜서 0이 최소가 되게
	private static void rotate(int cnt) {
		if(cnt == cctvs.size()) {
			//사각지대 영역 검사
			int total = check();
			if(total < ans) {
				ans = total; // 최소값갱신
//				for (int i = 0; i < R; i++) {
//					for (int j = 0; j < C; j++) {
//						System.out.print(copymap[i][j]+" ");
//					}
//					System.out.println();
//				}
//				System.out.println();
//				System.out.println(ans);
			}
			
			return;
		}
		int y = cctvs.get(cnt).y;
		int x = cctvs.get(cnt).x;
		int num = cctvs.get(cnt).num;
		for (int i = 0; i < dirs[num].length; i++) {
			setCCTV(y,x,dirs[num][i],1); // cctv 켜기
			rotate(cnt+1);
			setCCTV(y,x,dirs[num][i],-1); // cctv 끄기
		}

	}
	
	private static void setCCTV(int y, int x, int i, int val) {
		for (int k = 0; k < 4; k++) { //번호 상관없이 모두 4방향 탐색
			if((i & (1<<k)) > 0) {
				int ny = y;
				int nx = x;
				while(true) {
					ny += dy[k];
					nx += dx[k];
					if(ny >= R || ny < 0 || nx >= C || nx < 0) break;
					if(copymap[ny][nx] == 6) break;
					copymap[ny][nx] += val;
				}
			}
		}
		
	}

	private static int check() {
		int area = 0;
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if(copymap[i][j] == 0) {
					area++;
				}
			}
		}
		return area;
	}
	
	private static void copyMap() {
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				copymap[i][j] = map[i][j];
			}
		}
	}
}