🟦/백준
[골드 4] 감시
진뚱이용
2023. 5. 19. 20:47
https://www.acmicpc.net/problem/15683
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감
www.acmicpc.net
CCTV 마다 경우의 수가 존재하는구나
1번 CCTV: 우 하 좌 상
2번 CCTV: 우조아 하상
3번 CCTV: 상우 우하 하좌 좌상
4번 CCTV: 좌상우 상우하 우하좌 하좌상
5번 CCTV: 우하좌상
y : 0 ~ y-1 돌면서 안에서 x: 0 ~ x-1 돌 때
CCTV가 그리드 하게 가장 많이 비출수 있는 곳을 선택한다고 그게 최선의 답은 아니다
그럼 결국 모든 경우의 수를 돌려보아야 한다 -> 재귀
arrayList <CCTV>로 CCTV 모두 담아주고
ex) 1번 CCTV
오른쪽 비추고 다음 CCTV 재귀 호출
아래 비추고 다음 CCTV 재귀 호출
왼쪽 "
위 "
CCTV 모두 비췄을 때 방문하지 않았으며 벽이 아닌 곳 count
제일 작은 count가 정답이다
오른쪽 비추고 다음 CCTV재귀 호출
아래 비추고 다음 CCTV재귀 호출
이 사이에 오른쪽 비춘 visited를 false 해야 한다
근데 이전의 CCTV가 중복해서 비춘 것도 false로 만들기 때문에
맘 편하게 초기 visited를 visited_tmp에 복사해서 처리한다
import java.util.*;
class CCTV {
int y;
int x;
int number;
CCTV(int y, int x, int number) {
this.y = y;
this.x = x;
this.number = number;
}
}
class Main {
public static int answer = Integer.MAX_VALUE;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N, M;
int[][] array;
N = sc.nextInt();
M = sc.nextInt();
array = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++)
array[i][j] = sc.nextInt();
}
//////////////////////////////////////////////
ArrayList<CCTV> arrayList = new ArrayList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (array[i][j] != 0 && array[i][j] != 6)
arrayList.add(new CCTV(i, j, array[i][j]));
}
}
boolean[][] visited = new boolean[N][M];
recursion(array, arrayList, 0, visited);
System.out.println(answer);
}
public static void recursion(int[][] array, ArrayList<CCTV> arrayList, int cctv_index, boolean[][] visited) {
if (cctv_index == arrayList.size()) {
int count = 0;
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[i].length; j++) {
if (!visited[i][j] && array[i][j] != 6)
count++;
}
}
if (answer > count) answer = count;
return;
}
boolean[][] visited_tmp = new boolean[array.length][array[0].length];
CCTV CCTV_tmp = arrayList.get(cctv_index);
if (CCTV_tmp.number == 1) {
// 오른쪽
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[0].length; j++) {
visited_tmp[i][j] = visited[i][j];
}
}
for (int x = CCTV_tmp.x; x < array[0].length; x++) {
if (array[CCTV_tmp.y][x] == 6)
break;
visited_tmp[CCTV_tmp.y][x] = true;
}
recursion(array, arrayList, cctv_index + 1, visited_tmp);
// 왼쪽
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[0].length; j++) {
visited_tmp[i][j] = visited[i][j];
}
}
for (int x = CCTV_tmp.x; x >= 0; x--) {
if (array[CCTV_tmp.y][x] == 6)
break;
visited_tmp[CCTV_tmp.y][x] = true;
}
recursion(array, arrayList, cctv_index + 1, visited_tmp);
// 위
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[0].length; j++) {
visited_tmp[i][j] = visited[i][j];
}
}
for (int y = CCTV_tmp.y; y >= 0; y--) {
if (array[y][CCTV_tmp.x] == 6)
break;
visited_tmp[y][CCTV_tmp.x] = true;
}
recursion(array, arrayList, cctv_index + 1, visited_tmp);
// 아래
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[0].length; j++) {
visited_tmp[i][j] = visited[i][j];
}
}
for (int y = CCTV_tmp.y; y < array.length; y++) {
if (array[y][CCTV_tmp.x] == 6)
break;
visited_tmp[y][CCTV_tmp.x] = true;
}
recursion(array, arrayList, cctv_index + 1, visited_tmp);
} else if (CCTV_tmp.number == 2) {
// 오른쪽 왼쪽
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[0].length; j++) {
visited_tmp[i][j] = visited[i][j];
}
}
for (int x = CCTV_tmp.x; x < array[0].length; x++) {
if (array[CCTV_tmp.y][x] == 6)
break;
visited_tmp[CCTV_tmp.y][x] = true;
}
for (int x = CCTV_tmp.x; x >= 0; x--) {
if (array[CCTV_tmp.y][x] == 6)
break;
visited_tmp[CCTV_tmp.y][x] = true;
}
recursion(array, arrayList, cctv_index + 1, visited_tmp);
// 위 아래
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[0].length; j++) {
visited_tmp[i][j] = visited[i][j];
}
}
for (int y = CCTV_tmp.y; y >= 0; y--) {
if (array[y][CCTV_tmp.x] == 6)
break;
visited_tmp[y][CCTV_tmp.x] = true;
}
for (int y = CCTV_tmp.y; y < array.length; y++) {
if (array[y][CCTV_tmp.x] == 6)
break;
visited_tmp[y][CCTV_tmp.x] = true;
}
recursion(array, arrayList, cctv_index + 1, visited_tmp);
} else if (CCTV_tmp.number == 3) {
// 위 오른쪽
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[0].length; j++) {
visited_tmp[i][j] = visited[i][j];
}
}
for (int y = CCTV_tmp.y; y >= 0; y--) {
if (array[y][CCTV_tmp.x] == 6)
break;
visited_tmp[y][CCTV_tmp.x] = true;
}
for (int x = CCTV_tmp.x; x < array[0].length; x++) {
if (array[CCTV_tmp.y][x] == 6)
break;
visited_tmp[CCTV_tmp.y][x] = true;
}
recursion(array, arrayList, cctv_index + 1, visited_tmp);
// 오른쪽 아래
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[0].length; j++) {
visited_tmp[i][j] = visited[i][j];
}
}
for (int x = CCTV_tmp.x; x < array[0].length; x++) {
if (array[CCTV_tmp.y][x] == 6)
break;
visited_tmp[CCTV_tmp.y][x] = true;
}
for (int y = CCTV_tmp.y; y < array.length; y++) {
if (array[y][CCTV_tmp.x] == 6)
break;
visited_tmp[y][CCTV_tmp.x] = true;
}
recursion(array, arrayList, cctv_index + 1, visited_tmp);
// 아래 왼쪽
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[0].length; j++) {
visited_tmp[i][j] = visited[i][j];
}
}
for (int y = CCTV_tmp.y; y < array.length; y++) {
if (array[y][CCTV_tmp.x] == 6)
break;
visited_tmp[y][CCTV_tmp.x] = true;
}
for (int x = CCTV_tmp.x; x >= 0; x--) {
if (array[CCTV_tmp.y][x] == 6)
break;
visited_tmp[CCTV_tmp.y][x] = true;
}
recursion(array, arrayList, cctv_index + 1, visited_tmp);
// 왼쪽 위
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[0].length; j++) {
visited_tmp[i][j] = visited[i][j];
}
}
for (int x = CCTV_tmp.x; x >= 0; x--) {
if (array[CCTV_tmp.y][x] == 6)
break;
visited_tmp[CCTV_tmp.y][x] = true;
}
for (int y = CCTV_tmp.y; y >= 0; y--) {
if (array[y][CCTV_tmp.x] == 6)
break;
visited_tmp[y][CCTV_tmp.x] = true;
}
recursion(array, arrayList, cctv_index + 1, visited_tmp);
} else if (CCTV_tmp.number == 4) {
// 왼쪽 위 오른쪽
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[0].length; j++) {
visited_tmp[i][j] = visited[i][j];
}
}
for (int x = CCTV_tmp.x; x >= 0; x--) {
if (array[CCTV_tmp.y][x] == 6)
break;
visited_tmp[CCTV_tmp.y][x] = true;
}
for (int y = CCTV_tmp.y; y >= 0; y--) {
if (array[y][CCTV_tmp.x] == 6)
break;
visited_tmp[y][CCTV_tmp.x] = true;
}
for (int x = CCTV_tmp.x; x < array[0].length; x++) {
if (array[CCTV_tmp.y][x] == 6)
break;
visited_tmp[CCTV_tmp.y][x] = true;
}
recursion(array, arrayList, cctv_index + 1, visited_tmp);
// 위 오른쪽 아래
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[0].length; j++) {
visited_tmp[i][j] = visited[i][j];
}
}
for (int x = CCTV_tmp.x; x < array[0].length; x++) {
if (array[CCTV_tmp.y][x] == 6)
break;
visited_tmp[CCTV_tmp.y][x] = true;
}
for (int y = CCTV_tmp.y; y >= 0; y--) {
if (array[y][CCTV_tmp.x] == 6)
break;
visited_tmp[y][CCTV_tmp.x] = true;
}
for (int y = CCTV_tmp.y; y < array.length; y++) {
if (array[y][CCTV_tmp.x] == 6)
break;
visited_tmp[y][CCTV_tmp.x] = true;
}
recursion(array, arrayList, cctv_index + 1, visited_tmp);
// 오른쪽 아래 왼쪽
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[0].length; j++) {
visited_tmp[i][j] = visited[i][j];
}
}
for (int x = CCTV_tmp.x; x < array[0].length; x++) {
if (array[CCTV_tmp.y][x] == 6)
break;
visited_tmp[CCTV_tmp.y][x] = true;
}
for (int x = CCTV_tmp.x; x >= 0; x--) {
if (array[CCTV_tmp.y][x] == 6)
break;
visited_tmp[CCTV_tmp.y][x] = true;
}
for (int y = CCTV_tmp.y; y < array.length; y++) {
if (array[y][CCTV_tmp.x] == 6)
break;
visited_tmp[y][CCTV_tmp.x] = true;
}
recursion(array, arrayList, cctv_index + 1, visited_tmp);
// 아래 왼쪽 위
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[0].length; j++) {
visited_tmp[i][j] = visited[i][j];
}
}
for (int x = CCTV_tmp.x; x >= 0; x--) {
if (array[CCTV_tmp.y][x] == 6)
break;
visited_tmp[CCTV_tmp.y][x] = true;
}
for (int y = CCTV_tmp.y; y >= 0; y--) {
if (array[y][CCTV_tmp.x] == 6)
break;
visited_tmp[y][CCTV_tmp.x] = true;
}
for (int y = CCTV_tmp.y; y < array.length; y++) {
if (array[y][CCTV_tmp.x] == 6)
break;
visited_tmp[y][CCTV_tmp.x] = true;
}
recursion(array, arrayList, cctv_index + 1, visited_tmp);
} else {
// 오른쪽 왼쪽 아래 위
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[0].length; j++) {
visited_tmp[i][j] = visited[i][j];
}
}
for (int x = CCTV_tmp.x; x < array[0].length; x++) {
if (array[CCTV_tmp.y][x] == 6)
break;
visited_tmp[CCTV_tmp.y][x] = true;
}
for (int x = CCTV_tmp.x; x >= 0; x--) {
if (array[CCTV_tmp.y][x] == 6)
break;
visited_tmp[CCTV_tmp.y][x] = true;
}
for (int y = CCTV_tmp.y; y >= 0; y--) {
if (array[y][CCTV_tmp.x] == 6)
break;
visited_tmp[y][CCTV_tmp.x] = true;
}
for (int y = CCTV_tmp.y; y < array.length; y++) {
if (array[y][CCTV_tmp.x] == 6)
break;
visited_tmp[y][CCTV_tmp.x] = true;
}
recursion(array, arrayList, cctv_index + 1, visited_tmp);
}
}
}