백준 15683 : 감시

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

15683번: 감시

[ 문제풀이 ]

전형적인 시뮬레이션 문제이다. 감시 카메라가 가능한 모든 경우의 수를 돌려보면 쉽게 해결할 수 있다.

​모든 감시 카메라의 경우의 수를 구하고 감시 영역을 체크하는 부분을 각각 구현한다면 코드가 상당히 난잡해질 것이다.

1~5번 CCTV가 가능한 경우의 수가 그렇게 많지 않기 때문에 미리 배열로 어느 정도 선언한 후 구현한다면 코드도 간결해지고 구현하기가 더욱 쉬울 것이다.

​나는 배열을 통해 모든 CCTV의 회전 수, 가지고 있는 진행 방향 개수, 진행 방향에 따른 y, x 증가 값을 다음과 같이 선언하였다.

static int[] rotateCnt = {0, 4, 2, 4, 4, 1}; //1~5번 cctv가 가능한 회전 수
static int[] dirCnt = {0, 1, 2, 2, 3, 4}; //1~5번 cctv가 가지고 있는 방향 개수

//dir[a][b][c][d] : a번 cctv의 기준이 b일 경우 c번째 방향으로 y(0), x(1) 증가 값 
static int[][][][] dir = {{ },
		{{{0, 1}}, {{1, 0}}, {{0, -1}}, {{-1, 0}}},
		{{{0, -1}, {0, 1}}, {{-1, 0}, {1, 0}}},
		{{{-1, 0}, {0, 1}}, {{0, 1}, {1, 0}}, {{1, 0}, {0, -1}}, {{0, -1}, {-1, 0}}},
		{{{0, -1}, {-1, 0}, {0, 1}}, {{-1, 0}, {0, 1}, {1, 0}}, {{0, 1}, {1, 0}, {0, -1}}, {{1, 0}, {0, -1}, {-1, 0}}},
		{{{0, -1}, {-1, 0}, {0, 1}, {1, 0}}}};

전체 코드는 다음과 같다.

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

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;

	static int N, M, answer;
	static int[][] map, temp;
	
	static int[] rotateCnt = {0, 4, 2, 4, 4, 1}; //1~5번 cctv가 가능한 회전 수
	static int[] dirCnt = {0, 1, 2, 2, 3, 4}; //1~5번 cctv가 가지고 있는 방향 개수

	//dir[a][b][c][d] : a번 cctv의 기준이 b일 경우 c번째 방향으로 y(0), x(1) 증가 값 
	static int[][][][] dir = {{ },
							 {{{0, 1}}, {{1, 0}}, {{0, -1}}, {{-1, 0}}},
							 {{{0, -1}, {0, 1}}, {{-1, 0}, {1, 0}}},
							 {{{-1, 0}, {0, 1}}, {{0, 1}, {1, 0}}, {{1, 0}, {0, -1}}, {{0, -1}, {-1, 0}}},
							 {{{0, -1}, {-1, 0}, {0, 1}}, {{-1, 0}, {0, 1}, {1, 0}}, {{0, 1}, {1, 0}, {0, -1}}, {{1, 0}, {0, -1}, {-1, 0}}},
							 {{{0, -1}, {-1, 0}, {0, 1}, {1, 0}}}};
	

	static List<Cctv> ccvts, picks;

	static class Cctv {
		int y, x, number, flag;

		public Cctv(int y, int x, int number, int flag) {
			this.y = y;
			this.x = x;
			this.number = number;
			this.flag = flag; //cctv의 감시 영역 기준
		}
	}

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		answer = (int)1e9;
		map = new int[N][M];
		temp = new int[N][M];
		ccvts = new ArrayList<>();
		picks = new ArrayList<>();

		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());
				
				//모든 cctv를 리스트에 담음
				if (map[i][j] >= 1 && map[i][j] <= 5) {
					ccvts.add(new Cctv(i, j, map[i][j], -1));
				}
			}
		}

		pick_Cctv(0);

		bw.write(answer + "\n");
		bw.flush();bw.close();br.close();
	}

	//cctv가 가능한 모든 경우를 선택하는 함수
	public static void pick_Cctv(int idx) {
		if (picks.size() == ccvts.size()) {
			init();
			check();
			return;
		}

		for (int i = idx; i < ccvts.size(); ++i) {
			Cctv cctv = ccvts.get(i);

			//현재 cctv가 회전가능한 모든 기준을 선택
			for (int j = 0; j < rotateCnt[cctv.number]; ++j) {
				picks.add(new Cctv(cctv.y, cctv.x, cctv.number, j));
				pick_Cctv(i + 1);
				picks.remove(picks.size() - 1);
			}
		}
	}

	public static void init() {
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < M; ++j) {
				temp[i][j] = map[i][j];
			}
		}
	}

	//선택된 cctv를 모두 dfs를 돌려 감시영역 체크
	public static void check() {
		for (Cctv cctv : picks) {
			//현재 cctv의 기준으로 가지고 있는 모든 방향을 dfs
			for (int i = 0; i < dirCnt[cctv.number]; ++i) {
				dfs(cctv.y, cctv.x, cctv.number, cctv.flag, i);
			}
		}

		answer = Math.min(answer, getAnswer());
	}

	public static void dfs(int y, int x, int number, int flag, int d) {
		int ny = y + dir[number][flag][d][0];
		int nx = x + dir[number][flag][d][1];

		//영역을 벗어나거나 벽인 경우
		if (ny < 0 || nx < 0 || ny >= N || nx >= M) return;
		if (map[ny][nx] == 6) return;

		//다른 cctv가 존재하면 넘어감
		if (map[ny][nx] >= 1 && map[ny][nx] <= 5) {
			dfs(ny, nx, number, flag, d);
			return;
		}

		//감시 표시 후 dfs
		temp[ny][nx] = 7;
		dfs(ny, nx, number, flag, d);
	}

	public static int getAnswer() {
		int cnt = 0;

		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < M; ++j) {
				if (temp[i][j] == 0) cnt++;
			}
		}

		return cnt;
	}
}