[BOJ] 백준 15683 감시

[문제]

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

 

 

[소스 코드]

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

import javax.print.attribute.standard.NumberUpSupported;
public class Main {
	static class CCTV{
		int r,c,type;
		CCTV(int r,int c,int type){
			this.r = r;
			this.c = c;
			this.type = type;
		}
	}
	static int n,m;
	static int[][] copyM;
	static int result = 64;
	static int[] dr = {-1,0,1,0};
	static int[] dc = {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[][] map = new int[n][m];
		List<CCTV> list = new ArrayList<>();
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<m;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j]>=1 && map[i][j]<=5) {
					list.add(new CCTV(i,j,map[i][j]));
				}
			}
		}
		int total = (int)Math.pow(4,list.size());
		for(int t=0;t<total;t++) {
			int brute = t;
			copyM = new int[n][m];
			for(int i=0;i<n;i++) {
				copyM[i] = map[i].clone(); 
			}
			for(int k=0;k<list.size();k++) {
				int mode = brute % 4;
				brute /= 4;
				CCTV cctv = list.get(k);
				switch(cctv.type) {
				case 1:
					monitor(cctv.r,cctv.c,mode);
					break;
				case 2:
					monitor(cctv.r,cctv.c,mode);
					monitor(cctv.r,cctv.c,(mode+2)%4);
					break;
				case 3:
					monitor(cctv.r,cctv.c,mode);
					monitor(cctv.r,cctv.c,(mode+1)%4);
					break;
				case 4:
					monitor(cctv.r,cctv.c,mode);
					monitor(cctv.r,cctv.c,(mode+1)%4);
					monitor(cctv.r,cctv.c,(mode+2)%4);
					break;
				case 5:
					for(int i=0;i<4;i++) {
						monitor(cctv.r,cctv.c,(mode+i)%4);
					}
				}
			}
			int cnt = 0;
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					if(copyM[i][j]==0)
						cnt++;
				}
			}
			result = Math.min(result, cnt);
		}	
		System.out.println(result);
	}
	private static void monitor(int r,int c,int mode) {
		  int nr = r;
		  int nc = c;
		  while(true) {
			  nr = r + dr[mode];
			  nc = c + dc[mode];
			  if(nr<0 || nr>=n || nc<0 || nc>=m ||copyM[nr][nc]==6) break;
			  if(copyM[nr][nc]==0) {
				  copyM[nr][nc] = 7;
			  }
			  r = nr;
			  c = nc;
		  }
	}
}