[BOJ] 15683 감시

 

 

[문제]

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

 

 

[소스 코드]

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

public class Main {
	static class CCTV{
		int r,c,num;
		CCTV(int r,int c,int num){
			this.r = r;
			this.c = c;
			this.num = num;
		}
	}
	static int[][][] info = {
			{{},{},{},{}},
			{{0},{1},{2},{3}},
			{{0,2},{1,3},{},{}},
			{{0,1},{1,2},{2,3},{3,0}},
			{{0,1,3},{0,1,2},{1,2,3},{2,3,0}},
			{{0,1,2,3},{},{},{}}
	};
	static int[] dr = {-1,0,1,0};
	static int[] dc = {0,1,0,-1};
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int[][] map = new int[n][m];
		List<CCTV> cctv = 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]>0 && map[i][j]<6) {
					cctv.add(new CCTV(i,j,map[i][j]));
				}
			}
		}
		int result = Integer.MAX_VALUE;
		int total = (int)Math.pow(4, cctv.size());
		for(int i=0;i<total;i++) {
			int[][] copy = new int[n][m];
			for(int j=0;j<n;j++) copy[j] = map[j].clone();
			int mode = i;
			for(int j=0;j<cctv.size();j++) {
				int dir = mode % 4;
				mode /= 4;
				for(int d : info[cctv.get(j).num][dir]) {
					int nr = cctv.get(j).r + dr[d];
					int nc = cctv.get(j).c + dc[d];
					while(true) {
						if(nr<0 || nr>=n || nc<0 || nc>=m || map[nr][nc]==6) break;
						if(copy[nr][nc]==0) copy[nr][nc] = 7;
						nr += dr[d];
						nc += dc[d];
					}
				}
			}
			int cnt = 0;
			for(int r=0;r<n;r++) {
				for(int c=0;c<m;c++) {
					if(copy[r][c]==0) cnt++;
				}
			}
			result = Math.min(result, cnt);
		}
		System.out.println(result);
	}
}

 

배열 : 접근하지 않을 경우, 정해진 갯수만큼 배열 생성하지 않아도 된다