[백준] 감시

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

15683번: 감시

정말 다시는 만나고 싶지 않은 문제.. CCTV의 감시구역을 배열로 복사해서 넘기면 상대적으로 간단하게 풀 수 있지만 시간속도나 메모리 사용 여부를 줄여보고자 배열을 복사하지 않고 감시 구역을 체크해주고 DFS에서 돌아오면 다시 복구시키는 방식으로 해결하고자 했습니다. 이런 방식으로 풀 때 주의해야할 실수들은 다음과 같습니다.

 

1) 복구시키는 과정에서 중복으로 감시받는 위치

다른 CCTV에 의해 감시되고 있는 위치인데 현재 CCTV를 복구한다고 복구하다가 여전히 감시되는 위치를 지워버리는 경우가 있습니다. 저는 이 부분을 각각의 감시카메라의 번호만큼 board에서 빼줘서 중복으로 감시받는 위치를 체크해주었습니다.

 

2) dir인덱스 실수

0 ~ 3 인덱스를 사용해야하는데 4 인덱스를 사용하여 실수가 생겼습니다

 

3) CCTV가 없는 경우

CCTV가 없는 경우에는 모든 구역이 위험 구역이므로 체크해줘야합니다.

 

4) 빈 공간이 없는 경우

모든 위치가 벽이거나 CCTV인 경우에는 위험 구역이 없습니다. 

 

 

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

public class Main_15683 {
	static int n, m;
	static int[][] board;
	static ArrayList<int[]> cctv;
	static ArrayList<int[]> fives;
	
	static int[] dy = {0, 1, 0, -1};
	static int[] dx = {1, 0, -1, 0};
	
	static int ans = Integer.MAX_VALUE;
	static int count = 0;
	static int[] dirs;
	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		board = new int[n][m];
		cctv = new ArrayList<>();
		fives = new ArrayList<>();
		
		boolean isBlank = false;
		int cntOfBlank =0;
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < m; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
				if (board[i][j] == 0) {
					isBlank = true;
					cntOfBlank++;
				}
				//5번 CCTV는 바로 마킹시켜준다.(회전 필요 X)
				if (board[i][j] == 5) {
					fives.add(new int[] {i, j});
				}
				else if (board[i][j] > 0 && board[i][j] != 6) {
					cctv.add(new int[] {i, j});
				}
			}
		}
		
		if (!isBlank) {
			System.out.println(0);
			return;
		}
		
		if (fives.size() == 0 && cctv.size() == 0) {
			System.out.println(cntOfBlank);
			return;
		}
		
		for (int i = 0; i < fives.size(); i++) {
			int[] cur = fives.get(i);
			rotateFive(cur[0], cur[1]);
		}
		
		dfs(0);
		System.out.println(ans);
	}
	
	static int getAns() {
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (board[i][j] == 0) {
					cnt++;
				}
			}
		}
		
		return cnt;
	}
	
	static void dfs(int cnt) {
		if (cnt == cctv.size()) {
			count++;
			int ret = getAns();
			ans = Math.min(ret, ans);
			return;
		}
		
		int[] cur = cctv.get(cnt);
		
		int y = cur[0];
		int x = cur[1];
		
		int cctvType = board[y][x];
		
		switch(cctvType) {
			case 1:
				rotateOne(y, x, cnt);
				break;
			case 2:
				rotateTwo(y, x, cnt);
				break;
			case 3:
				rotateThree(y, x, cnt);
				break;
			case 4:
				rotateFour(y, x, cnt);
				break;
		}
	}
	
	static boolean inRange(int y, int x) {
		return 0 <= y && y < n && 0 <= x && x < m;
	}
	
	static void marking(int y, int x, int dir, int amount) {
		while(inRange(y, x) && board[y][x] != 6) {
			// CCTV가 아닌 경우
			if (board[y][x] <= 0) {
				board[y][x] -= amount;
			}
			
			y += dy[dir];
			x += dx[dir];
		}
	}
	
	static void restore(int y, int x, int dir, int amount) {
		while(inRange(y, x) && board[y][x] != 6) {
			// CCTV가 아닌 경우
			if (board[y][x] <= 0) {
				board[y][x] += amount;
			}
			
			y += dy[dir];
			x += dx[dir];
		}
	}
	
	static void rotateOne(int startY, int startX, int cnt) {
		for (int dir = 0; dir < 4; dir++) {
			marking(startY + dy[dir], startX + dx[dir], dir, 1);
			dfs(cnt + 1);
			restore(startY + dy[dir], startX + dx[dir], dir, 1);
		}
	}
	
	static void rotateTwo(int startY, int startX, int cnt) {
		int dir = 0;
		int dir2 = 2;
		
		for (int i = 0; i < 2; i++) {
			marking(startY + dy[dir + i], startX + dx[dir + i], dir + i, 2);
			marking(startY + dy[dir2 + i], startX + dx[dir2 + i], dir2 + i, 2);
			
			dfs(cnt + 1);
			
			restore(startY + dy[dir + i], startX + dx[dir + i], dir + i, 2);
			restore(startY + dy[dir2 + i], startX + dx[dir2 + i], dir2 + i, 2);
		}
	}
	
	static void rotateThree(int startY, int startX, int cnt) {
		int dir = 0;
		int dir2 = 3;
		
		for (int i = 0; i < 4; i++) {
			marking(startY + dy[dir + i], startX + dx[dir + i], dir + i, 3);
			marking(startY + dy[(dir2 + i) % 4], startX + dx[(dir2 + i) % 4], (dir2 + i) % 4, 3);
			
			dfs(cnt + 1);
			
			restore(startY + dy[dir + i], startX + dx[dir + i], dir + i, 3);
			restore(startY + dy[(dir2 + i) % 4], startX + dx[(dir2 + i) % 4],(dir2 + i) % 4, 3);
		}
	}	
	
	static void rotateFour(int startY, int startX, int cnt) {
		
		for (int dir = 0; dir < 4; dir++) {
			// dir을 제외한 방향 마킹
			for (int i = 0; i < 4; i++) {
				if (dir == i) {
					continue;
				}
				
				marking(startY + dy[i], startX + dx[i], i, 4);
			}
			
			dfs(cnt + 1);
			
			//dir을 제외한 방향 복구
			for (int i = 0; i < 4; i++) {
				if (dir == i) {
					continue;
				}
				restore(startY + dy[i], startX + dx[i], i, 4);
			}
		}
	}
	
	// 5번은 회전시킬 필요가 없다.
	static void rotateFive(int startY, int startX) {
		for (int i = 0; i < 4; i++) {
			marking(startY + dy[i], startX + dx[i], i, 5);

		}
	}
}