
https://www.acmicpc.net/problem/15683
문제분석
사무실에 설치된 CCTV의 방향을 적절히 회전시켜 사각지대의 최소 개수를 구하는 문제로, 각 CCTV가 가질 수 있는 방향 조합을 모두 탐색해야 하는 완전탐색(백트래킹) 문제이다. 먼저 입력을 통해 사무실의 지도와 CCTV의 위치를 저장하고, CCTV의 종류별로 가능한 감시 방향을 미리 배열로 정의한 뒤 DFS를 이용하여 각 CCTV의 방향 조합을 하나씩 선택해 나간다. 탐색 과정에서는 현재 상태의 지도를 복사한 뒤 선택한 방향으로 감시 범위를 표시하고 다음 CCTV로 재귀적으로 진행하며, 모든 CCTV의 방향이 결정된 경우에는 남아 있는 빈 칸(값이 0인 칸)을 계산하여 사각지대의 최소값을 갱신한다. 이때 감시는 지정된 방향으로 벽(6)을 만날 때까지 직선으로 진행되며, 다른 CCTV는 감시를 막지 않고 통과할 수 있다는 점에 주의해야 한다.
이 문제에서 가장 어려운 부분은 "구현"이다.
코드
import java.util.*;
import java.io.*;
public class Main {
static int[][][] dir = {
{}, // dummy
{ { 0 }, { 1 }, { 2 }, { 3 } }, // 1번 CCTV
{ { 0, 2 }, { 1, 3 } }, // 2번 CCTV
{ { 0, 1 }, { 1, 2 }, { 2, 3 }, { 3, 0 } }, // 3번 CCTV
{ { 0, 1, 2 }, { 1, 2, 3 }, { 2, 3, 0 }, { 3, 0, 1 } }, // 4번 CCTV
{ { 0, 1, 2, 3 } } // 5번 CCTV
};
// 0 위, 1 오른, 2 아래, 3 왼
static int[] dr = { -1, 0, 1, 0 };
static int[] dc = { 0, 1, 0, -1 };
static int[][] arr;// 0 빈칸, 6 벽, 1~5 CCTV(90도 회전 가능)
static int count = Integer.MAX_VALUE; // 안 가려지는 부분 최댓값 저장(CCTV 위치도 포함)
static ArrayList<int[]> cctv; // cctv 배열
static int N;
static int M;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); // 세로 크기
M = Integer.parseInt(st.nextToken()); // 가로 크기
arr = new int[N][M];
cctv = new ArrayList<>();
// 입력받고, cctv의 경우 따로 추가
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
int n = Integer.parseInt(st.nextToken());
arr[i][j] = n;
if (n > 0 && n < 6)
cctv.add(new int[] { i, j });
}
}
int[][] map = copy(arr); // 백트래킹용 array(복사해서 사용, 사각지대는 0)
DFS(0, map);
System.out.println(count);
}
// depth: cctv 인덱스. 해당 idx의 cctv를 회전시키는 모든 경우의 수로 배치한 뒤 재귀 DFS.
static void DFS(int depth, int[][] map) {
if(depth == cctv.size()){
count(map);
return;
}
int[] rc = cctv.get(depth);
// cctv 놓인 row,col
int row = rc[0];
int col = rc[1];
int type = arr[row][col];
for(int[] dest : dir[type]){
int[][] cloneMap = copy(map);
for(int d: dest){
watch(row,col,d,cloneMap);
}
DFS(depth + 1, cloneMap);
}
}
// map 복사해서 사용 -> 백트래킹 시 복원 안해도 되게끔
static int[][] copy(int[][] map) {
int[][] cloneMap = new int[N][M];
for (int i = 0; i < N; i++) {
cloneMap[i] = map[i].clone();
}
return cloneMap;
}
// map -1은 감시중인 지역
static void watch(int r, int c, int d, int[][] map) {
while (true) {
r += dr[d];
c += dc[d];
if (r < 0 || c < 0 || r >= N || c >= M)
break;
if (arr[r][c] == 6)
break;
if (map[r][c] == 0)
map[r][c] = -1;
}
}
static void count(int[][] map) {
int n = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 0) {
n += 1;
}
}
}
count = Math.min(count,n);
}
}

'알고리즘&PS > PS' 카테고리의 다른 글
| [JAVA] 백준 2293 동전 1 (0) | 2026.03.06 |
|---|---|
| [JAVA] 백준 11000 회의실 배정 (0) | 2026.03.06 |
| [JAVA] 백준 16928 뱀과 사다리 게임 (0) | 2026.03.05 |
| [JAVA] 백준 1753 최단경로 (0) | 2026.03.05 |
| [JAVA] 백준 1029 그림 교환 (0) | 2026.03.05 |