[백준] 15683 - 감시

[문제링크]

15683번: 감시

 

0. CCTV의 종류에 따라 가능한 모든 경우의 수를 해보는 브루트-포스 문제

  - 종류별로 가능한 탐색 방향을 미리 저장

 

1. 2/5번 CCTV는 회전 중 동일한 입력이 있으므로 제거해준다

  - 하지 않아도 통과하는데는 문제 없음

 

2. 매 CCTV마다, 가능한 모든 방향으로 감시해보며 다음으로 진행

  - 빈 공간(사각지대)의 개수를 유지, 최솟값 저장

 

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

public class Main{
	static int eArea, min=Integer.MAX_VALUE;
	static int[][] map;
	static ArrayList<int[]>cctv;
	static ArrayList<ArrayList<int[][]>>move;
	static void init() {
		move= new ArrayList<>();
		for (int i = 0; i <= 5; i++) {
			move.add(new ArrayList<>());
		}
		move.get(1).add(new int[][] {{1,0}});
		move.get(1).add(new int[][] {{0,1}});
		move.get(1).add(new int[][] {{-1,0}});
		move.get(1).add(new int[][] {{0,-1}});
		
		move.get(2).add(new int[][] {{0,-1},{0,1}});
		move.get(2).add(new int[][] {{1,0},{-1,0}});
		
		move.get(3).add(new int[][] {{1,0},{0,1}});
		move.get(3).add(new int[][] {{-1,0},{0,1}});
		move.get(3).add(new int[][] {{-1,0},{0,-1}});
		move.get(3).add(new int[][] {{1,0},{0,-1}});
		
		move.get(4).add(new int[][] {{1,0},{0,1},{-1,0}});
		move.get(4).add(new int[][] {{0,-1},{0,1},{-1,0}});
		move.get(4).add(new int[][] {{0,-1},{1,0},{-1,0}});
		move.get(4).add(new int[][] {{0,-1},{1,0},{0,1}});
		
		move.get(5).add(new int[][] {{-1,0},{0,-1},{1,0},{0,1}});
	}
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		init();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		
		map = new int[n+2][m+2];
		cctv=new ArrayList<>(); 
		for (int i = 0; i < n+2; i++) {
			map[i][0]=6; map[i][m+1]=6;
		}for (int i = 0; i < m+2; i++) {
			map[0][i]=6; map[n+1][i]=6;
		}
		for (int i = 1; i <= n; i++) {
			st=new StringTokenizer(br.readLine()," ");
			for (int j = 1; j <= m; j++) {
				map[i][j]=pint(st.nextToken());
				
				if(map[i][j]==0)eArea++;
				else if(map[i][j]!=6)cctv.add(new int[] {i,j});
			}
		}
		rec(0);
		System.out.println(min);
	}
	static void rec(int cnt) {
		if(cnt==cctv.size()) {
			min=Math.min(min, eArea);
			return;
		}
		
		int[][]mapBU=new int[map.length][map[0].length];
		for (int x = 0; x < map.length; x++)
			for (int y = 0; y < map[0].length; y++)
				mapBU[x][y]=map[x][y];
		int eAreaBU=eArea;
		
		int[] cur=cctv.get(cnt);
		int curV = map[cur[0]][cur[1]];
		
		for (int i = 0; i < move.get(curV).size(); i++) {
			for (int x = 0; x < map.length; x++)
				for (int y = 0; y < map[0].length; y++)
					map[x][y]=mapBU[x][y];
			eArea=eAreaBU;
			
			for (int j = 0; j < move.get(curV).get(i).length; j++) {
				int[]dir = move.get(curV).get(i)[j];
				int tx = cctv.get(cnt)[0]+dir[0], ty=cctv.get(cnt)[1]+dir[1];
				while(map[tx][ty]!=6) {
					if(map[tx][ty]==0) {
						map[tx][ty]=7;
						eArea--;
					}
					tx+=dir[0];
					ty+=dir[1];
				}
			}
			rec(cnt+1);
		}
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면