[백준] 15683번 감시 (시뮬레이션, java)

www.acmicpc.net/problem/15683

15683번: 감시

2번 감시카메라 방향 종류는 위아래 검사, 좌우 검사 2가지이고 

5번 감시카메라는 1가지 이다. (사방을 검사하기 때문에)

나머지 감시카메라의 방향 종류는 4가지이다. (90도 회전할 때마다 검사하는 곳이 달라진다)

 

나는 위를 검사할 때를 0 , 오른쪽 1, 아래쪽 2, 왼쪽을 3으로 인덱스를 둬서 각각 해당방향으로 cctv가 닿는 곳을 검색하는 함수를 따로 구현했다.

 

mark이차배열을 둬서 해당 위치의 cctv가 바라보는 방향 종류를 dfs로 돌리면서 저장하도록 하였다.

 

pos3차원 배열은 각 cctv번호의 dfs에서 고른 방향종류의 실제 cctv가 보는 방향을 저장하였다.

package algo0421;

import java.util.ArrayList;
import java.util.Scanner;

class Office{
	int y,x;

	public Office(int y, int x) {
		super();
		this.y = y;
		this.x = x;
	}
	
}

public class B_15683_감시_Main {
	static int n,m;
	static int[][] map;
	static int[][] mark;
	static int[][][] pos=new int[][][] 
			{{},{{0},{1},{2},{3}},{{0,2},{1,3}},{{0,1},{1,2},{2,3},{3,0}},{{0,1,3},{1,2,0},{1,2,3},{2,3,0}},
		{{0,1,2,3}}};//cctv번호, 선택한 방향조합 종류, 선택한 종류에 따른 방향
	static int answer=Integer.MAX_VALUE;
	static ArrayList<Office> list=new ArrayList<>();
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		map=new int[n][m];
		mark=new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				map[i][j]=sc.nextInt();
				if(map[i][j]!=6 && map[i][j]>0) {
					list.add(new Office(i,j));// 각 감시카메라의 좌표 저장 (추후 방향 dfs 돌리기 위해서)
				}
			}
		}
		
		dfs(0);
		System.out.println(answer);
	}
	private static void dfs(int idx) {
		if(idx==list.size()) {
			check();// 모든 감시카메라 방향 정해지면 사각지대 체크해본다.
			return;
		}
		int y=list.get(idx).y;
		int x=list.get(idx).x;
		int num=map[y][x];

		if(num==2) {
			for (int i = 0; i < 2; i++) {
				mark[y][x]=i;
				dfs(idx+1);
			}
		}else if(num==5) {
			mark[y][x]=0;
			dfs(idx+1);
		}else {// 1,3,4번 감시카메라의 가능한 방향
			for (int i = 0; i < 4; i++) {
				mark[y][x]=i;
				dfs(idx+1);
			}
		}
		
	}
	private static void check() {
		int[][] copy=new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <m; j++) {
				copy[i][j]=map[i][j];
			}
		}
		int total=0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if(map[i][j]==6) {
					total+=1;
					continue;
				}
				if(map[i][j]>0) {//cctv일때
					int num=map[i][j];
					total+=1;
					for (int k = 0; k < pos[num][mark[i][j]].length; k++) {
						int dir=pos[num][mark[i][j]][k];
						if(dir==0) {
							total+=up(i,j,copy);
						}else if(dir==1) {
							total+=right(i,j,copy);
						}else if(dir==2) {
							total+=down(i,j,copy);
						}else {
							total+=left(i,j,copy);
						}
					}
				}
			}
		}
		if(answer>n*m-total)answer=n*m-total;
		
	}
	private static int right(int i, int j,int[][] copy) {
		int cnt=0;
		for (int x = j+1; x < m; x++) {
			if(copy[i][x]==6)break;
			if(copy[i][x]==0) {
				copy[i][x]=-1;
				cnt+=1;
			}
		}
		return cnt;
	}
	private static int left(int i, int j,int[][] copy) {
		int cnt=0;
		for (int x = j-1; x>=0; x--) {
			if(copy[i][x]==6)break;
			if(copy[i][x]==0) {
				cnt+=1;
				copy[i][x]=-1;
			}
		}
		return cnt;
	}
	private static int up(int i, int j,int[][] copy) {
		int cnt=0;
		for (int y = i-1; y>=0; y--) {
			if(copy[y][j]==6)break;
			if(copy[y][j]==0) {
				copy[y][j]=-1;
				cnt+=1;
			}
		}
		return cnt;
	}
	
	private static int down(int i, int j,int[][] copy) {
		int cnt=0;
		for (int y = i+1; y<n; y++) {
			if(copy[y][j]==6)break;
			if(copy[y][j]==0) {
				cnt+=1;
				copy[y][j]=-1;
			}
		}
		return cnt;
	}
}