Java
import java.util.*;
public class Main {
/*
1.어떤 방식으로 문제에 접근해야 되는가?
변수(cctv)들이 가질 수 있는 값이 여러개, 변수들이 가질 수 있는 모든 조합을 확인
1번 cctv의 방향 - 4
2번 cctv의 방향 - 2
3번 cctv의 방향 - 4
4번 cctv의 방향 - 4
5번 cctv의 방향 - 1
cctv가 볼 수 있는 방향이 최대 4이므로 4진법(0~3)을 사용해서 모든 방향의 조합을 확인
ex) 1번 cctv만 있는 경우
0(동), 1(북), 2(서), 3(남) -> 0~3까지 총 4개 방향
ex) 1번 cctv가 2대 있는 경우
00, 01, 02, 03, 10, 11, 12, 13, 20, 21, 22, 23, 30, 31, 32, 33 -> 0~15까지 총 16개 방향
이 경우는 cctv의 방향이 총4인 것들만 고려되었기 때문에 2,5번 cctv로 조합을 구성하는 경우 중복되는 방향이 발생
중복된 계산이 있어도 시간 내로 통과되기 때문에 최대 방향 기준으로 고려했음
2.cctv 개수별 모든 방향의 조합
0대 -> 0
1대 -> 3
2대 -> 15
n대 -> 4^n(cctv 개수)-1
3.10진수를 4진수로 변환하는 방법
ex) cctv가 1대인 경우
4가지 방향(0~3)
for(int total = 0; total < 4; total++)
int cnt = total
for(int size=0;size<1;size++)
cnt % 4 -> 0, 1, 2, 3
cnt = cnt / 4
ex) cctv가 2대인 경우
16가지 방향(0~15)
for(int total = 0; total < 16; total++)
int cnt = total
for(int size=0;size<2;size++)
cnt % 4 -> 00,10,20,30,01,11,21...33
cnt = cnt / 4
4.각 cctv별 방향에 대해서 cctv가 볼 수 있는 방향에 대해서 방문처리
5.각 cctv 방향에 대한 방문처리가 끝났으면 사각지대(0)의 개수를 계산하고 최소 사각지대인지 확인
6.cctv별 모든 방향에 대해서 최소 사각지대를 체크(4~5번 반복)
*/
static Scanner sc = new Scanner(System.in);
static int n, m;
static int[][] board1 = new int[10][10]; // 사무실 칸 정보
static int[][] board2 = new int[10][10]; // 사각지대 개수를 계산할 사무실 칸
static ArrayList<int[]> cctv = new ArrayList<int[]>(); // cctv 개수
static int[] dx = new int[]{1,0,-1,0}; // 남 -> 동 -> 북 -> 서
static int[] dy = new int[]{0,1,0,-1};
static public long cctvEntireCase(int base, int exponent) {
long result = 1;
for(int i=0;i<exponent;i++) {
result = result * base;
}
return result;
}
// (x,y)에서 dir 방향으로 진행하면서 벽을 만날 때 까지 지나치는 모든 빈칸을 7로 바꿔버림
static public void dirMove(int x, int y, int dir) {
dir = dir % 4; // (3,5) -> (3,1) 4진수(0~3)까지의 방향으로 고정시킴
while(true) {
x += dx[dir];
y += dy[dir];
if(OutOfBound(x, y) || board2[x][y] == 6) break;
if(board2[x][y] != 0) continue;
board2[x][y] = 7;
}
}
static public Boolean OutOfBound(int x, int y) {
if(x < 0 || x >= n || y < 0 || y >= m) return true;
else return false;
}
static public int solution(int n, int m) {
int minEmptyCnt = 0; // 사각지대 최소 개수(답)
// 사무실 칸 정보 입력
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
board1[i][j] = sc.nextInt();
if(board1[i][j] != 0 && board1[i][j] != 6)
cctv.add(new int[]{i,j});
if(board1[i][j] == 0)
minEmptyCnt++;
}
}
// cctv별 모든 방향에 대해서 사각지대 최소 개수 체크
long entireCase = cctvEntireCase(4, cctv.size());
if(entireCase == 1) entireCase = 0; // cctv가 0개인 경우
for(int i=0;i<entireCase;i++) {
// cctv의 모든 방향에 대해서 각각 사각지대 계수를 따로 계산
// 원본 사무실 칸 정보는 변하면 안되고 사본을 가지고 계산해야됨
for(int a=0;a<n;a++) {
for(int b=0;b<m;b++) {
board2[a][b] = board1[a][b];
}
}
int tmp = i;
for(int cctvDir=0;cctvDir<cctv.size();cctvDir++) {
int dir = tmp % 4;
tmp = tmp / 4;
int[] pos = cctv.get(cctvDir); // cctv 좌표를 저장하고 있는 List에서 n번째 cctv의 좌표
int x = pos[0];
int y = pos[1];
if(board1[x][y] == 1) {
dirMove(x, y, dir);
}else if(board1[x][y] == 2) {
dirMove(x, y, dir);
dirMove(x, y, dir+2);
}else if(board1[x][y] == 3) {
dirMove(x, y, dir);
dirMove(x, y, dir+1);
}else if(board1[x][y] == 4) {
dirMove(x, y, dir);
dirMove(x, y, dir+1);
dirMove(x, y, dir+2);
}else if(board1[x][y] == 5) {
dirMove(x, y, dir);
dirMove(x, y, dir+1);
dirMove(x, y, dir+2);
dirMove(x, y, dir+3);
}
}
int cnt = 0;
for(int a=0;a<n;a++) {
for(int b=0;b<m;b++) {
if(board2[a][b] == 0) cnt++;
}
}
if(cnt < minEmptyCnt) minEmptyCnt = cnt;
}
return minEmptyCnt;
}
public static void main(String[] args) {
n = sc.nextInt();
m = sc.nextInt();
int result = solution(n,m);
System.out.println(result);
}
}
