문제
N x M 크기의 사무실에 1~5번 CCTV와 벽(6)이 있다. 각 CCTV는 번호에 따라 감시할 수 있는 방향이 다르고 회전이 가능하다. 모든 CCTV의 방향을 결정했을 때, 사각지대(감시되지 않는 빈 칸)의 최솟값을 구하는 문제이다.
- 1번: 1방향 감시 (상/하/좌/우 중 하나)
- 2번: 2방향 감시 (서로 반대 방향 2개, 상하 or 좌우)
- 3번: 2방향 감시 (90도 각도 2개)
- 4번: 3방향 감시
- 5번: 4방향 감시 (전방향)
입력
첫째 줄에 N(1 ≤ N ≤ 8)과 M(1 ≤ M ≤ 8)이 주어진다. 다음 N줄에 M개의 값이 주어진다. 0은 빈 칸, 6은 벽, 1~5는 해당 CCTV이다. CCTV의 개수는 최대 8개이다.
출력
사각지대의 최솟값을 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 6 0 0 0 0 0 0 0 | 20 |
풀이
각 CCTV의 방향을 DFS로 모든 경우로 시도하면서, 각 조합에서 사각지대 수의 최솟값을 구하는 완전탐색이다.
- 맵을 읽으면서 CCTV 위치와 종류를 리스트에 저장하고, 초기 빈 칸 수(
cnt)를 센다. cDir배열로 각 CCTV 종류별 가능한 방향 조합을 미리 정의한다.dfs(idx, remine, map)에서 idx번 CCTV의 모든 방향 조합을 순서대로 시도한다. 방향 선택 후 해당 방향으로 관찰(observation)하고 사각지대 수를 감소시킨다.- 모든 CCTV 방향 결정 후 현재 사각지대 수와 전역 최솟값
ans를 비교해 갱신한다. - 다음 방향 시도를 위해 맵을 원상 복구한다(
copy메서드로 백업/복원).
핵심 아이디어: CCTV 수가 최대 8개이고 각 방향 조합은 최대 4가지이므로 최대 4^8 = 65,536가지 경우만 탐색한다. 맵 배열을 깊이 복사하여 상태 백트래킹을 구현한다.
코드
package com.ssafy.an.day149;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Day141BOJ15683감시브루트포스 { // 15683 감시
static int N, M, ans, cnt;
static int[] dr = { -1, 0, 1, 0 }, dc = { 0, 1, 0, -1 };
static int[][][] cDir = { //
{ { 0 } }, // 미사용
{ { 1 }, { 2 }, { 3 }, { 0 } }, // 1
{ { 1, 3 }, { 0, 2 } }, // 2
{ { 0, 1 }, { 1, 2 }, { 2, 3 }, { 3, 0 } }, // 3
{ { 0, 1, 3 }, { 0, 1, 2 }, { 1, 2, 3 }, { 2, 3, 0 } }, // 4
{ { 0, 1, 2, 3 } } // 5
};
static List<int[]> cctv;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
cnt = 0;
int[][] map = new int[N][M];
cctv = 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());
if (map[i][j] == 0)
cnt++;
else if (map[i][j] > 0 && map[i][j] != 6)
cctv.add(new int[] { i, j, map[i][j] });
}
}
ans = cnt;
dfs(0, cnt, map);
System.out.println(ans);
br.close();
}
private static void dfs(int idx, int remine, int[][] map) {
if (idx == cctv.size()) {
ans = Math.min(ans, remine);
return;
}
int[][] tmp = copy(map);
int[] cc = cctv.get(idx);
for (int i = 0; i < cDir[cc[2]].length; i++) {
int c = 0;
for (int j = 0; j < cDir[cc[2]][i].length; j++) {
int d = cDir[cc[2]][i][j];
c += observation(cc[0], cc[1], d, tmp);
}
dfs(idx + 1, remine - c, tmp);
tmp = copy(map);
}
}
private static int observation(int r, int c, int d, int[][] map) {
int cnt = 0;
while (true) {
r += dr[d];
c += dc[d];
if (r < 0 || r >= N || c < 0 || c >= M || map[r][c] == 6)
break;
if ((map[r][c] >= 1 && map[r][c] <= 5) || map[r][c] == -1)
continue;
map[r][c] = -1;
cnt++;
}
return cnt;
}
private static int[][] copy(int[][] map) {
int[][] tmp = new int[N][];
for (int i = 0; i < N; i++)
tmp[i] = map[i].clone();
return tmp;
}
}복잡도
- 시간: O(4^C * N * M) — C는 CCTV 수(최대 8), 각 방향 조합 탐색 후 관찰에 O(N*M)
- 공간: O(N * M)