BJ15683 감시

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

이 문제는 벽과 5가지의 CCTV가 입력으로 주어지고, 씨씨티비의 방향을 적절히 정해 사각지대의 최소 크기를 구하는 것이다.

CCTV를 배열에 담아두고, 각 씨씨티비의 방향을 돌려가며 모든 경우의 수를 탐색하는 방식으로 구현했다.

package day0218;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class CCTV {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static tv[] tvs;
	static int[][] dir = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
	static int N, M, cnt_tv, answer = Integer.MAX_VALUE;

	static public class tv {
		int x, y;
		int state;

		public tv(int x, int y, int state) {
			this.x = x;
			this.y = y;
			this.state = state;
		}
	}

	static int check_blind(int[][] map) {
		int count = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 0)
					count++;
			}
		}
		return count;
	}

	static void solve(int[][] map, int n_tv) {
		if (n_tv == cnt_tv) {
			int tmp = check_blind(map);
			// print(map);
			// System.out.println();
			if (tmp < answer) {
				answer = tmp;
			}
			return;
		}
		switch (tvs[n_tv].state) { // CCTV의 번호에 따라 경우의수만큼 재귀함수를 호출.
		case 1:
			for (int d = 0; d < 4; d++) {
				int[][] nextmap = beam(map, tvs[n_tv].x, tvs[n_tv].y, d);
				solve(nextmap, n_tv + 1);
			}
			break;
		case 2:
			for (int cas = 0; cas < 2; cas++) {
				if (cas == 0) {
					int[][] nextmap = beam(map, tvs[n_tv].x, tvs[n_tv].y, 0);
					nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 1);
					solve(nextmap, n_tv + 1);
				} else {
					int[][] nextmap = beam(map, tvs[n_tv].x, tvs[n_tv].y, 2);
					nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 3);
					solve(nextmap, n_tv + 1);
				}
			}
			break;
		case 3:
			for (int cas = 0; cas < 4; cas++) {
				if (cas == 0) {
					int[][] nextmap = beam(map, tvs[n_tv].x, tvs[n_tv].y, 0);
					nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 2);
					solve(nextmap, n_tv + 1);
				} else if (cas == 1) {
					int[][] nextmap = beam(map, tvs[n_tv].x, tvs[n_tv].y, 0);
					nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 3);
					solve(nextmap, n_tv + 1);
				} else if (cas == 2) {
					int[][] nextmap = beam(map, tvs[n_tv].x, tvs[n_tv].y, 1);
					nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 2);
					solve(nextmap, n_tv + 1);
				} else if (cas == 3) {
					int[][] nextmap = beam(map, tvs[n_tv].x, tvs[n_tv].y, 1);
					nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 3);
					solve(nextmap, n_tv + 1);
				}
			}
			break;
		case 4:
			for (int cas = 0; cas < 4; cas++) {
				if (cas == 0) {
					int[][] nextmap = beam(map, tvs[n_tv].x, tvs[n_tv].y, 1);
					nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 2);
					nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 3);
					solve(nextmap, n_tv + 1);
				} else if (cas == 1) {
					int[][] nextmap = beam(map, tvs[n_tv].x, tvs[n_tv].y, 0);
					nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 2);
					nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 3);
					solve(nextmap, n_tv + 1);
				} else if (cas == 2) {
					int[][] nextmap = beam(map, tvs[n_tv].x, tvs[n_tv].y, 0);
					nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 1);
					nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 3);
					solve(nextmap, n_tv + 1);
				} else if (cas == 3) {
					int[][] nextmap = beam(map, tvs[n_tv].x, tvs[n_tv].y, 0);
					nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 1);
					nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 2);
					solve(nextmap, n_tv + 1);
				}
			}
			break;
		case 5:
			int[][] nextmap = beam(map, tvs[n_tv].x, tvs[n_tv].y, 0);
			nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 1);
			nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 2);
			nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 3);
			solve(nextmap, n_tv + 1);
			break;
		}
	}

	static int[][] beam(int[][] map, int x, int y, int d) { // CCTV가 감시하는 부분을 맵에 색칠함. int d에 따라 동, 서, 남, 북.
		int[][] tmp_map = new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				tmp_map[i][j] = map[i][j];
			}
		}
		while (x >= 0 && x < N && y >= 0 && y < M) {
			if (map[x][y] == 6) {
				break;
			}
			tmp_map[x][y] = 9; // 감시구역이면 9로 초기화.
			x += dir[d][0];
			y += dir[d][1];
		}
		return tmp_map;
	}

	static void print(int[][] map) { // 맵을 출력.
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				System.out.print(map[i][j]);
			}
			System.out.println();
		}
	}

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		int[][] map = new int[N][M];
		cnt_tv = 0;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] > 0 && map[i][j] < 6) {
					cnt_tv++;
				}
			}
		}
		tvs = new tv[cnt_tv];
		int c = 0;
		for (int i = 0; i < N; i++) { // CCTV의 정보를 tvs 배열에 담음.
			for (int j = 0; j < M; j++) {
				if (map[i][j] > 0 && map[i][j] < 6) {
					tvs[c++] = new tv(i, j, map[i][j]);
				}
			}
		}
		solve(map, 0);

		System.out.println(answer);
	}
}