문제 바로가기 : https://www.acmicpc.net/problem/15683
메모리 : 56844KB
시간 : 344ms
언어 : Java 11
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.concurrent.BrokenBarrierException;
class Main {
static int[][] board;
static int N, M;
static List<Pair> cctvList = new ArrayList<>();
static int cctvCount;
static int minCount = Integer.MAX_VALUE;
static class Pair {
int x, y, type;
Pair(int x, int y, int type) {
this.x = x;
this.y = y;
this.type = type;
}
}
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());
board = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
if (board[i][j] != 0 && board[i][j] != 6) {
cctvList.add(new Pair(i, j, board[i][j]));
}
}
}
cctvCount = cctvList.size();
dfs(0, board);
System.out.println(minCount);
}
static void dfs(int index, int[][] map) {
if (index == cctvCount) {
int count = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 0) {
count++;
}
}
}
minCount = Math.min(minCount, count);
return;
}
Pair cctv = cctvList.get(index);
int x = cctv.x;
int y = cctv.y;
int type = cctv.type;
int[][] newMap;
switch (type) {
case 1:
for (int i = 0; i < 4; i++) {
newMap = copyMap(map);
watch(newMap, x, y, i);
dfs(index + 1, newMap);
}
break;
case 2:
for (int i = 0; i < 2; i++) {
newMap = copyMap(map);
watch(newMap, x, y, i);
watch(newMap, x, y, i + 2);
dfs(index + 1, newMap);
}
break;
case 3:
for (int i = 0; i < 4; i++) {
newMap = copyMap(map);
watch(newMap, x, y, i);
watch(newMap, x, y, (i + 1) % 4);
dfs(index + 1, newMap);
}
break;
case 4:
for (int i = 0; i < 4; i++) {
newMap = copyMap(map);
watch(newMap, x, y, i);
watch(newMap, x, y, (i + 1) % 4);
watch(newMap, x, y, (i + 2) % 4);
dfs(index + 1, newMap);
}
break;
case 5:
newMap = copyMap(map);
watch(newMap, x, y, 0);
watch(newMap, x, y, 1);
watch(newMap, x, y, 2);
watch(newMap, x, y, 3);
dfs(index + 1, newMap);
break;
}
}
static void watch(int[][] map, int x, int y, int dir) {
int nx = x;
int ny = y;
while (true) {
nx += dx[dir];
ny += dy[dir];
if (nx < 0 || nx >= N || ny < 0 || ny >= M || map[nx][ny] == 6) {
break;
}
if (map[nx][ny] == 0) {
map[nx][ny] = -1;
}
}
}
static int[][] copyMap(int[][] map) {
int[][] newMap = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
newMap[i][j] = map[i][j];
}
}
return newMap;
}
static int[] dx = { 0, 1, 0, -1 };
static int[] dy = { 1, 0, -1, 0 };
}
귀찮은 구현문제ㅜ CCTV를 돌려가면서 사각지대의 개수를 세 주면 된다.
'Algorithm' 카테고리의 다른 글
[Algo] 백준 1937 욕심쟁이 판다 JAVA (0) | 2024.05.08 |
---|---|
[Algo] 백준 15650 N과 M(2) JAVA (0) | 2024.05.08 |
[Algo] 백준 9252 LCS2 JAVA (0) | 2024.05.08 |
[Algo] 백준 10942 팰린드롬? JAVA (0) | 2024.05.08 |
[Algo] 백준 2251 물통 JAVA (0) | 2024.05.08 |