백준 - 감시 (15683)

1. 문제

문제 링크

2. 풀이

2-1. 조건

1. CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다.
2. CCTV는 벽을 통과할 수 없다.
3. CCTV는 가로, 세로 방향으로만 감시할 수 있다.
4. CCTV끼리는 통과할 수 있다.

2-2. 풀이

DFS를 활용해서 CCTV가 감시하는 모든 경우의 수를 탐색하는 문제입니다.
주먹구구식으로 CCTV의 번호에 따라서
switch문이나 if문으로 어떤 방향으로 감시를 하라고 코딩을 할 순 있지만
그렇게 하면 코드가 난잡해지고 디버깅도 어려우니까
역시 테이블을 하나 정의해보겠습니다.

계획 1 - 감시 테이블을 정의합니다.

static final int[][][] CCTV = {
	{{0}, {1}, {2}, {3}}, // 1번 CCTV는 [[북], [동], [남], [서]]를 감시 가능
	{{1, 3}, {0, 2}}, // 2번 CCTV는 [[동, 서], [북, 동]]를 감시 가능
	{{0, 1}, {0, 3}, {2, 3}, {1, 2}},// 이하 생략...
	{{0, 1, 2}, {0, 2, 3}, {1, 2, 3}, {0, 1, 3}},
	{{0, 1, 2, 3}},
};

1~5번 CCTV들이 각각 어떤 방향으로 얼만큼 감시할 수 있는지 정의했습니다.
이제 이 테이블만 바라보고 감시를 구현하면 됩니다.

계획2 - 감시를 구현합니다.

static void watch(int[] dirs, int y, int x) {
        // 원본 좌표 저장
	int oriY = y;
    	int oriX = x;
		
        // CCTV가 한 번에 감시할 수 있는 방향에 대해 감시 
	for (int i = 0; i < dirs.length; i++) {
		int[] way = DIRS[dirs[i]];
		int plusY = way[0];
        	int plusX = way[1];
			
		y = oriY + plusY;
		x = oriX + plusX;
			
                // 사무실의 범위를 벗어나지 않고 벽이 아닐 때까지
		while (0 <= y && y < N && 0 <= x && x < M && map[y][x] != 6) {
                        // 다른 CCTV가 아닐 때
			if (map[y][x] < 1  || map[y][x] > 5) map[y][x] = -1;
				
			y += plusY;
			x += plusX;
		}
	}
}

인자로 받는 int[] dirs는 우리가 위에서 정의한 테이블의 한 요소입니다.
이 요소를 통해 감시를 편하게 구현할 수 있습니다.

계획3 - 감시하는 모든 경우의 수를 탐색합니다.

// 감시하는 모든 경우의 수를 탐색
static int min(int depth) {
	// 기저 사례 - 모든 CCTV가 감시중일 때 사각지대의 개수를 리턴
	if (depth == CNT) {
		int ret = 0;
			
		for (int i = 0; i < N; i++) 
			for (int j = 0; j < M; j++) 
				if (map[i][j] == 0) ret++;
					
		return ret;
	}
		
	int[] coordinate = cctv.get(depth); // CCTV 좌표
	int y = coordinate[0];
	int x = coordinate[1];
	int ret = MAX;
	final int[][] camera = CCTV[map[y][x] - 1]; // 현재 CCTV가 감시할 수 있는 모든 경우들
	int[][] tmp = new int[N][M]; // 이전 상황을 저장할 배열
		
	copy(tmp, map);
		
	for (int i = 0; i < camera.length; i++) {
		watch(camera[i], y, x); // i번째 경우에 대해서 감시
		ret = Math.min(ret, min(depth + 1));
		copy(map, tmp);
	}
		
	return ret;
}

2번 계획에서 만든 watch함수를 통해서 감시하는 모든 경우를 구현했습니다.

3. 전체 코드

import java.util.List;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	// 계획 1 - 감시 테이블을 정의합니다.
	static final int[][][] CCTV = {
		{{0}, {1}, {2}, {3}},
		{{1, 3}, {0, 2}},
		{{0, 1}, {0, 3}, {2, 3}, {1, 2}},
		{{0, 1, 2}, {0, 2, 3}, {1, 2, 3}, {0, 1, 3}},
		{{0, 1, 2, 3}},
	};
	static final int[][] DIRS = {
			{-1, 0}, {0, 1}, {1, 0}, {0, -1}
	};
	static int[][] map;
	static int N, M, CNT, MAX = 987654321;
	static List<int[]> cctv = new ArrayList<>(); // CCTV를 담을 배열
	
	// 계획3 - 감시하는 모든 경우의 수를 탐색합니다.
	static int min(int depth) {
		// 기저 사례 - 모든 CCTV가 감시중일 때 사각지대의 개수를 리턴
		if (depth == CNT) {
			int ret = 0;
			
			for (int i = 0; i < N; i++) 
				for (int j = 0; j < M; j++) 
					if (map[i][j] == 0) ret++;
					
			return ret;
		}
		
		int[] coordinate = cctv.get(depth); // CCTV 좌표
		int y = coordinate[0];
		int x = coordinate[1];
		int ret = MAX;
		final int[][] camera = CCTV[map[y][x] - 1]; // 현재 CCTV가 감시할 수 있는 모든 경우들
		int[][] tmp = new int[N][M]; // 이전 상황을 저장할 배열
		
		copy(tmp, map);
		
		for (int i = 0; i < camera.length; i++) {
			watch(camera[i], y, x); // i번째 경우에 대해서 감시
			ret = Math.min(ret, min(depth + 1));
			copy(map, tmp);
		}
		
		return ret;
	}
	
	// 계획2 - 감시를 구현합니다.
	static void watch(int[] dirs, int y, int x) {
		// 원본 좌표 저장
		int oriY = y;
		int oriX = x;
		
		// CCTV가 한 번에 감시할 수 있는 방향에 대해 감시 
		for (int i = 0; i < dirs.length; i++) {
			int[] way = DIRS[dirs[i]];
			int plusY = way[0];
			int plusX = way[1];
			
			y = oriY + plusY;
			x = oriX + plusX;
			
			// 사무실의 범위를 벗어나지 않고 벽이 아닐 때까지
			while (0 <= y && y < N && 0 <= x && x < M && map[y][x] != 6) {
				// 다른 CCTV가 아닐 때
				if (map[y][x] < 1  || map[y][x] > 5) map[y][x] = -1;
				
				y += plusY;
				x += plusX;
			}
		}
	}
	
	static void copy(int[][] a, int[][] b) {
		for (int i = 0; i < N; i++) 
			for (int j = 0; j < M; j++) 
				a[i][j] = b[i][j];
	}
	
	public static void main(String[] args) throws Exception {
		String[] s = br.readLine().split(" ");
		
		N = Integer.parseInt(s[0]);
		M = Integer.parseInt(s[1]);
		
		map = new int[N][M];
		
		for (int i = 0; i < N; i++) {
			s = br.readLine().split(" ");
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(s[j]);
				
				// 1~5일 때 CCTV를 리스트에 저장
				if (1 <= map[i][j] && map[i][j] <= 5) cctv.add(new int[] {i, j});
			}
		}
		
		CNT = cctv.size();
		
		bw.write(min(0) + "");
		bw.close();
	}
}