백준 15683 감시 (Java)

1. 문제 링크

15683번: 감시

 

2. 문제 및 입출력예제

 

3. 문제 풀이

5가지 종류의 CCTV가 있고 사각지대를 최소로 만들어야 하는 문제이다.

CCTV 객체 리스트를 이용해 CCTV의 위치와 종류를 저장한다.

중복순열로 CCTV 방향을 정해서 각각 방향에서 벽이 나오기 전까지 큐에 CCTV를 계속 넣으면서 진행한다.

단계가 다 끝난 후 현재 순열에서의 사각지대를 계산한다.

모든 순열이 끝난 후 최소 사각지대 수를 출력한다.

 

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;

public class Main {
	static class CCTV{
		int x;
		int y;
		int num;
		public CCTV(int x, int y, int num) {
			super();
			this.x = x;
			this.y = y;
			this.num = num;
		}
		
	}
	private static int N, M, result = Integer.MAX_VALUE;
	private static int map[][], mapClone[][];
	private static int[] dx = {-1, 1, 0, 0}; //상하좌우
	private static int[] dy = {0, 0, -1, 1};
	private static ArrayList<CCTV> list; //CCTV 배열
	private static int[] numbers; //순열에서 뽑힌 숫자들
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] nm = br.readLine().split(" ");
		N = Integer.parseInt(nm[0]);
		M = Integer.parseInt(nm[1]);
		list = new ArrayList<>(); 
		map = new int[N][M]; //0은 빈칸, 1~5는 CCTV, 6은 벽
		int temp;
		for(int i=0;i<N;i++) {
			String[] split = br.readLine().split(" ");
			for(int j=0;j<M;j++) {
				temp = Integer.parseInt(split[j]);
				map[i][j] = temp;
				if(temp!=0 && temp!=6) {
					list.add(new CCTV(i, j, temp));
				}
			}
		} 
		
		numbers = new int[list.size()];
		permutation(0);
		
		System.out.println(result);
	}


	private static void permutation(int cnt) {
		if(cnt == list.size()) {
			mapClone = new int[N][M];
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					mapClone[i][j] = map[i][j];
				}
			}
			
			for(int i=0;i<list.size();i++) {
				direction(list.get(i), numbers[i]); //cctv 번호랑 뽑힌 방향에 맞게 설정
			}
			findArea();
			return;
		}
		
		for(int i=0;i<4;i++) {
			numbers[cnt] = i;
			permutation(cnt+1);
		}
	}

	private static void direction(CCTV cctv, int d) {
		int num = cctv.num;
		if(num == 1) {
			watch(cctv, d);
		}
		else if(num == 2) {
			if(d==0 || d==1) {
				watch(cctv, 0);
				watch(cctv, 1);
			}
			else {
				watch(cctv, 2);
				watch(cctv, 3);
			}
		}
		else if(num == 3) {
			if(d == 0) { //위, 오
				watch(cctv, 0);
				watch(cctv, 3);
			}
			else if(d == 1) { //오, 아
				watch(cctv, 3);
				watch(cctv, 1);
			}
			else if(d == 2) { //아, 왼
				watch(cctv, 1);
				watch(cctv, 2);
			}
			else { //왼, 위
				watch(cctv, 2);
				watch(cctv, 0);
			}
		}//위0 아1 왼2 오3
		else if(num == 4) {
			if(d == 0) { //위, 오, 아
				watch(cctv, 0);
				watch(cctv, 3);
				watch(cctv, 1);
			}
			else if(d == 1) { //오, 아, 왼
				watch(cctv, 3);
				watch(cctv, 1);
				watch(cctv, 2);
			}
			else if(d == 2) { //아, 왼, 위
				watch(cctv, 1);
				watch(cctv, 2);
				watch(cctv, 0);
			}
			else { //왼, 위, 오
				watch(cctv, 2);
				watch(cctv, 0);
				watch(cctv, 3);
			}
		}
		else {
			watch(cctv, 0);
			watch(cctv, 1);
			watch(cctv, 2);
			watch(cctv, 3);
		}
	}

	//bfs
	private static void watch(CCTV cctv, int d) {
		Queue<CCTV> queue = new ArrayDeque<>();
		boolean[][] visit = new boolean[N][M];
		
		queue.offer(cctv);
		visit[cctv.x][cctv.y] = true;
		
		while(!queue.isEmpty()) {
			CCTV now = queue.poll();
			int X = now.x + dx[d];
			int Y = now.y + dy[d];
			if(X<0 || X>=N || Y<0 || Y>=M  || mapClone[X][Y] == 6) {
				break;
			}
			
			if(mapClone[X][Y] == 0) {
				mapClone[X][Y] = -1;
			}
			queue.offer(new CCTV(X, Y, cctv.num));
		}
		
	}
	
	private static void findArea() {
		int count = 0;
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(mapClone[i][j] == 0) {
					count++;
				}
			}
		}
		result = Math.min(result, count);
	}
}