[백준] 구현 - 15683: 감시 (Java)

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

15683번: 감시

	import java.io.*;
	import java.util.*;
	// 감시
	@SuppressWarnings("unchecked")
	class Main {
	static int n, m, size = Integer.MAX_VALUE, cctvCount;
	static int[][] area, copyMap, dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
	static boolean[][] visit;
	static ArrayList<CCTV> cctvList = new ArrayList<>();
	static class CCTV {
	int x;
	int y;
	int num;
	CCTV(int x, int y, int num) {
	this.x = x;
	this.y = y;
	this.num = num;
	}
	}
	public static void main(String[] args) throws IOException {
	input();
	process();
	}
	static void input() throws 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());
	area = new int[n + 1][m + 1];
	visit = new boolean[n + 1][m + 1];
	for (int i = 1; i <= n; i++) {
	st = new StringTokenizer(br.readLine());
	for (int j = 1; j <= m; j++) {
	area[i][j] = Integer.parseInt(st.nextToken());
	if (area[i][j] > 0 && area[i][j] < 6) {
	cctvList.add(new CCTV(i, j, area[i][j]));
	}
	}
	}
	cctvCount = cctvList.size();
	}
	static void process() {
	func(0, 0, area);
	System.out.println(size);
	}
	static void func(int depth, int start, int[][] map) {
	if (cctvCount == 0) {
	copy(area);
	size = checkArea();
	return;
	}
	if (cctvCount == depth) {
	int width = checkArea();
	size = Math.min(size, width);
	return;
	}
	for (int i = 0; i < 4; i++) {
	copy(map);
	CCTV cctv = cctvList.get(start);
	if (cctv.num == 2 || cctv.num == 5) {
	if (i == 2)
	break;
	if (cctv.num == 5 && i == 1)
	break;
	}
	changeView(cctv, i);
	func(depth + 1, start + 1, copyMap);
	}
	}
	static void copy(int[][] map) {
	copyMap = new int[n + 1][m + 1];
	for (int i = 0; i <= n; i++) {
	for (int j = 0; j <= m; j++) {
	copyMap[i][j] = map[i][j];
	}
	}
	}
	static void changeView(CCTV cctv, int direction) {
	switch(cctv.num) {
	case 1:
	bfs(direction, cctv);
	break;
	case 2:
	bfs(direction, cctv);
	bfs((direction + 2) % 4, cctv);
	break;
	case 3:
	bfs(direction, cctv);
	bfs((direction + 1) % 4, cctv);
	break;
	case 4:
	bfs(direction, cctv);
	bfs((direction + 1) % 4, cctv);
	bfs((direction + 2) % 4, cctv);
	break;
	case 5:
	bfs(direction, cctv);
	bfs((direction+1) % 4, cctv);
	bfs((direction+2) % 4, cctv);
	bfs((direction+3) % 4, cctv);
	break;
	}
	}
	static void bfs(int direction, CCTV cctv) {
	int x = cctv.x;
	int y = cctv.y;
	while(true) {
	x += dir[direction][0];
	y += dir[direction][1];
	if (x < 1 || y < 1 || x > n || y > m) break;
	if (copyMap[x][y] == 6) break;
	if (copyMap[x][y] > 1 && copyMap[x][y] < 6) continue;
	copyMap[x][y] = 7;
	}
	}
	static int checkArea() {
	int width = 0;
	for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= m; j++) {
	if (copyMap[i][j] == 0) {
	width++;
	}
	}
	}
	return width;
	}
	}

view raw A15683.java hosted with ❤ by GitHub

완전탐색에 더 가까운 문제이다.

CCTV번호 별로 나눠서 방향에 알맞게 감시영역을 체크해주면 풀리는 문제이다.

처음에는 감시영역을 7로 체크하고 returnView() 메서드를 만들어서 func 메서드의 반복문 마지막에서 감시영역을 다시 0으로 바꿔줬다.

CCTV가 여러개일 때 감시영역이 겹쳐 감시가 되고있음에도 0이되어서 배열을 복사해서 해결했다.

또한 CCTV가 없는 경우가 있었다.

난이도는 어렵지 않지만 지금까지 푼 문제중 가장 긴 코드가 나왔다. 이게 맞나 했던 접근방법이 맞았다.