백준_15683_감시

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

문제를 보면 Cctv 5개가 있고 (1 ~ 5) 번 벽은 6으로 표현된다

먼저 문제를 이해해보면 1,3,4 번 Cctv는 총 4 가지 방법으로 감시할 수 있고 

2 번은 2가지, 5 번은 1가지 밖에없다.

 

그럼 씨씨 티브이가 주어졌을 때 감시할 수 있는 모든 경우의 수를 구하면 된다.

 

예를 들어 2번과 3번과 5번이 주어졌다고 가정하자. 모든 경우를 각각 구한 후 감시할 수 있는 영역이

최대인 경우를 구하면 된다.(감시하지 못하는 영역의 최솟값을 구하는 문제)

 

2번은 (왼쪽, 오른쪽), (위, 아래) 두 가지! 

3번은 4가지! 

5번은 1가지! 

 

나는 모든 경우를 탐색하기 위해서 재귀를 이용하였다. 

(숫자)는 Cctv 가 가리킬 수 있는 방향의 가짓수 중 하나라고 생각하고 설명하였다.   

그럼 2번 Cctv 가 (1) 인경우(예를 들어 왼쪽, 오른쪽 방향일 때) 3번 Cctv는 (1) ~ (4) 4가지 방향으로 가르킬수있고

5번 Cctv 는 1가지 밖에 없기 때문에 총 4가지 경우가 있다. 

2번 Cctv가 (2) 인경우도 마찬가지이다. 

     2번 Cctv     3번 Cctv     5번 Cctv 

        (1)  =>      (1)    =>     (1) 

                       (2)    =>     (1)

                       (3)    =>     (1) 

                       (4)    =>     (1)           

 

        (2)  =>      (1)    =>     (1)

                       (2)    =>     (1)

                       (3)    =>     (1) 

                       (4)    =>     (1)

 

이런 식으로 생각하고 코드를 구현하였다.

다음은 전체 코드이다.

  

 

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

public class Main {
		static int n,m;
		static int[][] map;
		static int ans = Integer.MAX_VALUE;
		static ArrayList<Cctv> list;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		list = new ArrayList<Cctv>();
		n = sc.nextInt();
		m = sc.nextInt();
		
		map = new int[n + 1][m + 1];
		
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= m; j++) {
				int value = sc.nextInt();
				map[i][j] = value;
                //Cctv 인 위치는 리스트에 저장
				if(value >= 1 && value <= 5) {
					list.add(new Cctv(i, j, value));
				}
			}
		}
		see(0, map);
		System.out.println(ans);
	}
	static void see(int index, int[][] arr) {
	
    // 리스트에담긴 모든 씨시티비를 탐색한경우 사각지대에 최소값을 구함
		if(index == list.size()) {
			int count = 0;
			for(int i = 1; i <= n; i++) {
				for(int j = 1; j <= m; j++) {
					if(arr[i][j] == 0) {
						count++;
					}
				}
			}
			ans = Math.min(ans, count);
			return;
		}
		int x = list.get(index).x;
		int y = list.get(index).y;
		int num = list.get(index).CctvNum;
		// index 번째 Cctv를 찾고 index 번째 Cctv 가질수 있는 모든 방향을 구해준다
		switch (num) {
		case 1:
        	//1번 CcTV 의경우 4가지의 방향을 가질수있음
			for(int i = 0; i < 4; i++) {
            	// 새로운 배열에 담아줌 4가지 방향의 경우를 각각 구해야하기 때문!
				int[][] copy = new int[n + 1][m + 1];
				for(int j = 1; j <= n; j++) {
					for(int k = 1; k <= m; k++) {
						copy[j][k] = arr[j][k];
					}
				}
                // for 문을 돌면서 각경우에 감시할수있는곳들을 확인하고 다음 Cctv로 넘어간다.
				rotate(copy, x, y, i);
				see(index + 1, copy);
			}
			break;
		case 2:
			for(int i = 0; i < 2; i++) {
				int[][] copy = new int[n + 1][m + 1];
				for(int j = 1; j <= n; j++) {
					for(int k = 1; k <= m; k++) {
						copy[j][k] = arr[j][k];
					}
				}
                // 2번 Cctv 는 2방향으로 감시하기떄문에 rotate 함수가 두개!
				rotate(copy, x, y, i);
				rotate(copy, x, y, i + 2);
				see(index + 1, copy);
			}
			break;
		case 3:
			for(int i = 0; i < 4; i++) {
				int[][] copy = new int[n + 1][m + 1];
				for(int j = 1; j <= n; j++) {
					for(int k = 1; k <= m; k++) {
						copy[j][k] = arr[j][k];
					}
				}
				rotate(copy, x, y, i);
				rotate(copy, x, y, (i + 1) % 4);
				see(index + 1, copy);
			}
			break;
		case 4:
			for(int i = 0; i < 4; i++) {
				int[][] copy = new int[n + 1][m + 1];
				for(int j = 1; j <= n; j++) {
					for(int k = 1; k <= m; k++) {
						copy[j][k] = arr[j][k];
					}
				}
				rotate(copy, x, y, i);
				rotate(copy, x, y, (i + 1) % 4);
				rotate(copy, x, y, (i + 2) % 4);
				see(index + 1, copy);
			}
			break;
		case 5:	
				int[][] copy = new int[n + 1][m + 1];
				for(int j = 1; j <= n; j++) {
					for(int k = 1; k <= m; k++) {
						copy[j][k] = arr[j][k];
					}
				}
				rotate(copy, x, y, 0);
				rotate(copy, x, y, 1);
				rotate(copy, x, y, 2);
				rotate(copy, x, y, 3);
				see(index + 1, copy);
			
			break;
		}
	}
    // Cctv 의 위치 가 x, y 이고 dir 방향일때의 감시하는곳들을 7로 표시해준다
	static void rotate(int[][] arr, int x, int y, int dir) {
		switch (dir) {
        	// 위쪽 방향인경우 (예를들어 Cctv의 위치가 (5,3) 이였다면 위쪽 방향이기떄문에 
            					(4, 3), (3, 3), (2, 3) ~~ 이런식으로 구해주면된다.)
			case 0:
				for(int i = x; i >= 1 ; i--) {
					if(arr[i][y] == 6) {
						break;
					}
					arr[i][y] = 7;
				}
				break;
			case 1:
				for(int i = y; i <= m ; i++) {
					if(arr[x][i] == 6) {
						break;
					}
					arr[x][i] = 7;
				}
				break;
			case 2:
				for(int i = x; i <= n ; i++) {
					if(arr[i][y] == 6) {
						break;
					}
					arr[i][y] = 7;
				}
				break;
			case 3:
				for(int i = y; i >= 1 ; i--) {
					if(arr[x][i] == 6) {
						break;
					}
					arr[x][i] = 7;
				}
				break;
		}
	}
}

class Cctv{

	int x;
	int y;
	int CctvNum;
	
	public Cctv(int x, int y, int CctvNum) {
		this.x = x;
		this.y = y;
		this.CctvNum = CctvNum;
	}
	
}