[백준][13458][Java] 시험 감독

www.acmicpc.net/problem/15683

15683번: 감시

문제풀이

CCTV 갯수의 제한이 8개이고, 5종류의 CCTV들을 종류 상관없이 4번씩 돌린다고 가정 했을때 그렇게 값이 크지 않아서 DFS해도 되겠구나 생각하였다.

 

CCTV의 자리는 List에 넣어서 관리해주었다. CCTV의 갯수만큼 배열을 만들어서 각 CCTV 마다 시작 방향(동서남북)을 중복순열로 체크하였다. 벽을 만나거나 범위를 넘어가기 전까지 2차원 map 배열에 감시범위를 표시할 함수를 따로 선언하였고, 1번 CCTV는 한 번, 2번은 반대방향으로 한번 더, 나머지 3~5번은 각 CCTV번호 -1 만큼 반복해서 map에 범위를 표시하였다.

 

그리고 마지막에 map에 0 갯수를 체크하여 min을 최신화 해주었다.

코드

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

public class Main{
	static int N,M, min, cctvIndex;
	static int[][] map, mapCopy;
	static int[] dx = {0,1,0,-1};
	static int[] dy = {1,0,-1,0};
	static int[] isSelected;
	static List<Pos> cctvList;
	
	public static void main(String[] args) throws NumberFormatException, 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());
		cctvList = new ArrayList<>();
		map = new int[N][M];
		mapCopy = new int[N][M];
		min = Integer.MAX_VALUE;
		
		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(0<map[i][j] && map[i][j] <6) {
					cctvList.add(new Pos(i,j));
					cctvIndex++;
				}
			}
		}
		
		isSelected = new int[cctvIndex];
		permutation(0);
		
		System.out.println(min);
	}
	private static void permutation(int cnt) {
		if(cnt == cctvIndex) {
			//맵 카피
			for(int i=0; i<N; i++) {
				for(int j=0; j<M; j++) {
					mapCopy[i][j] = map[i][j]; 
				}
			}
			
			//cctv종류에 따라 맵에 체크
			for(int i=0; i<cctvList.size(); i++) {
				Pos pos = cctvList.get(i);
				int cctvNum = map[pos.x][pos.y];
				
				int dis = isSelected[i];
				
				switch(cctvNum) {
				case 1:
					checkCctv(pos.x, pos.y, dis);
					break;
				case 2:
					checkCctv(pos.x, pos.y, dis);
					checkCctv(pos.x, pos.y, (dis+2)%4);
					break;
				case 3:
				case 4:
				case 5:
					for(int j=0; j<cctvNum-1; j++) {
						int a = (dis+j)%4;
						checkCctv(pos.x, pos.y, a);
					}
					break;
				}
			}
			
			//사각지대 갯수 체크 and 최소값
			int area =0;
			for(int i=0; i<N; i++) {
				for(int j=0; j<M; j++) {
					if(mapCopy[i][j] == 0) area++; 
				}
			}
			
			min = Math.min(min, area);
			return;
		}
		
		for(int i=0; i<4; i++) {
			isSelected[cnt] = i;
			permutation(cnt+1);
		}
	}
	
	public static void checkCctv(int x, int y, int dis) {
		while(true) {
			x += dx[dis];
			y += dy[dis];
			
			if(x<0 || x>=N || y<0 || y>=M || mapCopy[x][y] == 6) break;
			// cctv
			if(0<mapCopy[x][y] && mapCopy[x][y] <6) continue;
			
			mapCopy[x][y] = 9;
		}
	}
	
	static class Pos{
		int x;
		int y;
		public Pos(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
}