백준 15683번 감시 (JAVA)

 

삼성 기출인만큼, 시뮬레이션 문제이다. 테스트케이스의 지도 크기가 1 <= N, M <=8로 작았고, CCTV의 최대 개수가 8개를 넘지 않는다하였으므로 완전탐색을 사용하여도 시간초과가 나지않으리라는 확신을 얻을 수 있었다. 

따라서 로직을 아래와 같이 세웠다.

 

1. 지도를 입력받는다. 지도를 입력받으면서, cctv의 위치와 종류를 Node 클래스로 받아 리스트에 저장한다.

for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = stoi(st.nextToken());
				if (map[i][j] >= 1 && map[i][j] < 6) {
					cctv.add(new Node(i, j, map[i][j]));
				}
			}
		}

2. 리스트를 선택 비선택의 방식으로 순회하면서 모든 방향회전의 경우의 수를 따진다.

	private static void solve(int pos) {
		if (pos == cctv.size()) {
			countBlindSpot();
			return;
		}
		int[][] tmp = deepCopy(map);
		Node c = cctv.get(pos);
		for (int i = 0; i < rotation[c.cctv]; i++) {
			for (int j = 0; j < dir[c.cctv - 1][i].length; j += 2) {
				int nx = dir[c.cctv - 1][i][j];
				int ny = dir[c.cctv - 1][i][j + 1];
				view(c, nx, ny);
			}
			solve(pos + 1);
			map = deepCopy(tmp);
		}

	}

회전하기 전에 tmp 임시 배열에 복사해두었다가, 탐색이 끝나고나면 복구시킨 후 다음 회전을 보는 것도 추가해주었다.

이후 pos가 cctv 리스트의 사이즈에 도달하면, 사각지대의 숫자를 센다.

private static void countBlindSpot() {
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 0) {
					cnt++;
				}
			}
		}
		minBS = Math.min(minBS, cnt);
	}

 

코드 전문은 아래와 같다.

package samsung;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ_15683번_감시 {
	static int[][][] dir = { { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } }, // 1번 CCTV
			{ { 0, 1, 0, -1 }, { 1, 0, -1, 0 } }, // 2번 CCTV
			{ { -1, 0, 0, 1 }, { 0, 1, 1, 0 }, { 1, 0, 0, -1 }, { 0, -1, -1, 0 } }, // 3번 CCTV
			{ { 0, 1, -1, 0, 1, 0 }, { 0, 1, -1, 0, 0, -1 }, { 0, -1, -1, 0, 1, 0 }, { 0, -1, 0, 1, 1, 0 } }, // 4번 CCTV
			{ { 0, 1, -1, 0, 1, 0, 0, -1 } }, // 5번 CCTV
	};
	static int[] rotation = { 0, 4, 2, 4, 4, 1 };
	static int N, M, map[][];
	static List<Node> cctv = new ArrayList<>();

	static int minBS = Integer.MAX_VALUE;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		map = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = stoi(st.nextToken());
				if (map[i][j] >= 1 && map[i][j] < 6) {
					cctv.add(new Node(i, j, map[i][j]));
				}
			}
		}
		solve(0);
		System.out.println(minBS);
	}

	private static void solve(int pos) {
		if (pos == cctv.size()) {
			countBlindSpot();
			return;
		}
		int[][] tmp = deepCopy(map);
		Node c = cctv.get(pos);
		for (int i = 0; i < rotation[c.cctv]; i++) {
			for (int j = 0; j < dir[c.cctv - 1][i].length; j += 2) {
				int nx = dir[c.cctv - 1][i][j];
				int ny = dir[c.cctv - 1][i][j + 1];
				view(c, nx, ny);
			}
			solve(pos + 1);
			map = deepCopy(tmp);
		}

	}

	private static void view(Node c, int dx, int dy) {
		int nx = c.x;
		int ny = c.y;
		while (true) {
			nx = nx + dx;
			ny = ny + dy;
			if (!isValid(nx, ny)) {
				break;
			}
			if (map[nx][ny] == 6) {
				break;
			}
			if (map[nx][ny] != 0) {
				continue;
			}
			map[nx][ny] = -1;
		}
	}

	private static void countBlindSpot() {
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 0) {
					cnt++;
				}
			}
		}
		minBS = Math.min(minBS, cnt);
	}

	static class Node {
		int x;
		int y;
		int cctv;

		Node(int x, int y, int cctv) {
			this.x = x;
			this.y = y;
			this.cctv = cctv;
		}
	}

	private static int[][] deepCopy(int[][] src) {
		int[][] result = new int[src.length][src[0].length];
		for (int i = 0; i < src.length; i++) {
			System.arraycopy(src[i], 0, result[i], 0, src[0].length);
		}
		return result;
	}

	private static boolean isValid(int x, int y) {
		return 0 <= x && 0 <= y && x < N && y < M;
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}

}