풀이
아이디어
-
경우의 수
- 먼저 몇 번의 사건이 발생하는지 보면, cctv가 방향을 정하는 사건이 몇번 일어날까? cctv의 개수만큼 사건이 발생한다. 그리고 각각의 사건당 4방향이니까 4가지의 경우의 수가 있다. cctv의 개수가 3대라면 444= 4^3 =64가지다. 최대 8대라면 4^8 = 6만정도 나와서 완전탐색을 쓸 수 있다.
- 즉, 4방향^cctv의 개수다. -> 각 사건의 경우의 수^사건의 횟수.
- 중복순열: 서로 다른 n개중 r개를 중복을 허락하여 선택하여 일렬로 나열하는 경우 -> n^r
-
입력받을 때, 0을 카운트하고 cctv가 확보할 수 있는
0의 최대범위를 구해서 빼면 최소 사각지대가 나온다. -> cctv, 벽은 카운트하지 않고 0만 카운트한다. -
재귀를 이용한다. 한 대의 cctv의 방향을 정한다음 재귀를 호출해서 다음 cctv의 방향을 정한다. 그렇게 반복하다가 모든 cctv의 방향을 정했을 때가 기저조건이다.
구현
3가지 포인트가 있었다.
-
한 대의 cctv의 방향을 정하고 다음 카메라의 방향을 정했을 때, 겹치는 0이 있어서 중복 카운트 될 수 있다.
-> 중복을 피하기 위해서 방문을 기록하는 map과 똑같은 크기의 이차원 배열이 필요하다. (전역배열 vis) -
재귀를 돌고 다시 돌아와서 cctv를 다음 방향으로 돌리기 전에 원상복귀를 해야한다.
- 재귀 복귀를 했을 때, 다시 해당 함수의 처음 위치까지 거꾸로 가면서 방문을 취소하는 방법도 생각했었는데, 그러면 방문표시는 되어있지만 그 방향에서 방문을 하지 않았던 위치까지 취소를 시키는 문제가 발생할 수 있다.
->해당 cctv의, 해당 방향에서,방문을 하는 그 위치들을 기록해둬야한다. 여러 위치를 방문하기 때문에 ArrayList 생성.(tmpVisited)
-> 또한 그 방향에서 카운트한 것도 취소해야하는데, tmpVisited.size()를 이용해서 빼준다.
-
중복되는 위치가 있을 때, 그 위치를 표시한 cctv의 방향이 원상복귀되면서 방문이 취소되면 원래 다른 cctv가 방문을 할 수 있었던 위치였기때문에 카운트가 부족해지는지를 고민했었다.
-> 재귀는 stack 자료구조이기 때문에 중복되는 위치를 방문 표시한 재귀함수는 가장 늦게 리턴받고 따라서 가장 늦게 원상복귀된다.
코드
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
/**
* 감시
* 완전탐색 -> cctv 최대 8개 & 1번 카메라 4방향 가능 -> 4^8 = 6만개
* 입력받을 때, 0을 카운트하고 cctv가 확보할 수 있는 0의 최대범위를 구해서 빼면 최소 사각지대가 나온다.
* @author dnflr
*
*/
public class Main_15683_이광용 {
static int n, m, tmpMaxCnt, maxCnt, zeroCnt, ans;
static int[][] map;
static ArrayList<Point> list;
static int dx[] = {0, -1, 0, 1}; //우 상 좌 하
static int dy[] = {1, 0, -1, 0};
static boolean[][] vis;
static class Point {
int x, y;
Point(int x , int y){
this.x = x;
this.y = y;
}
}
static void recur(int cctvIdx) {
if(cctvIdx == list.size()) {
//최대값 비교
maxCnt = Math.max(maxCnt, tmpMaxCnt);
return;
}
int tmpX = list.get(cctvIdx).x;
int tmpY = list.get(cctvIdx).y;
int x = map[tmpX][tmpY];
switch (x) {
case 1:
for(int i = 0; i < 4; i++) { //4가지 방향
int nx = tmpX+dx[i];
int ny = tmpY+dy[i];
//이번 방향에 대해서 방문한 점들을 모두 저장하고 나중에 재귀가 돌아왔을때, 다시 원복해준다.
ArrayList<Point> tmpVisited = new ArrayList<>();
while(nx >= 0 && nx < n && ny >= 0 && ny < m) {
//6인 경우, 거기까지 break하고 재귀로 다음 cctv를 탐색한다
if( map[nx][ny] == 6) break;
//혹시 CCTV 자리거나 이미 방문한 곳이라면 지나간다.
if( map[nx][ny] == 0 && vis[nx][ny] == false) {
tmpMaxCnt++;
vis[nx][ny] = true;
tmpVisited.add(new Point(nx, ny));
}
nx += dx[i];
ny += dy[i];
//방문한자리 체크하고 재귀 부르고
//다시 왔을때... 방문 풀고 그럴려면 방문을 기억해둬야함...
//이번에 증가된 cnt도 함께 원복 해야하는데 그건 이번 방향에서 방문한 tmpVisited의 사이즈로 하면됨
}
recur(cctvIdx+1);
//원상복귀
tmpMaxCnt -= tmpVisited.size();
for(Point p : tmpVisited) {
vis[p.x][p.y]= false;
}
}
break;
case 2:
for(int i = 0; i < 2; i++) { //2가지 방향-> 오른쪽과 왼쪽 / 위쪽과 아래쪽
int nx = tmpX+dx[i];
int ny = tmpY+dy[i];
//이번 방향에 대해서 방문한 점들을 모두 저장하고 나중에 재귀가 돌아왔을때, 다시 원복해준다.
ArrayList<Point> tmpVisited = new ArrayList<>();
while(nx >= 0 && nx < n && ny >= 0 && ny < m) {//오른쪽 or 위쪽
//6인 경우, 거기까지 break하고 재귀로 다음 cctv를 탐색한다
if( map[nx][ny] == 6) break;
//혹시 CCTV 자리거나 이미 방문한 곳이라면 지나간다.
if( map[nx][ny] == 0 && vis[nx][ny] == false) {
tmpMaxCnt++;
vis[nx][ny] = true;
tmpVisited.add(new Point(nx, ny));
}
nx += dx[i];
ny += dy[i];
}
//반대쪽 확인 : 왼쪽 or 아래쪽
nx = tmpX+dx[i+2]; //다시 방향 맞춰서 초기화
ny = tmpY+dy[i+2];
while(nx >= 0 && nx < n && ny >= 0 && ny < m) {
//6인 경우, 거기까지 break하고 재귀로 다음 cctv를 탐색한다
if( map[nx][ny] == 6) break;
//혹시 CCTV 자리거나 이미 방문한 곳이라면 지나간다.
if( map[nx][ny] == 0 && vis[nx][ny] == false) {
tmpMaxCnt++;
vis[nx][ny] = true;
tmpVisited.add(new Point(nx, ny));
}
nx += dx[i+2];
ny += dy[i+2];
}
recur(cctvIdx+1);
//원상복귀
tmpMaxCnt -= tmpVisited.size();
for(Point p : tmpVisited) {
vis[p.x][p.y]= false;
}
}
break;
case 3:
for(int i = 0; i < 4; i++) { //4가지 방향-> 오른쪽과 위쪽/ 위쪽과 왼쪽
//왼쪽과 아래쪽 / 아래쪽과 오른쪽
int nx = tmpX+dx[i];
int ny = tmpY+dy[i];
//이번 방향에 대해서 방문한 점들을 모두 저장하고 나중에 재귀가 돌아왔을때, 다시 원복해준다.
ArrayList<Point> tmpVisited = new ArrayList<>();
//총 두 방향 확인 : 첫번째 방향
//오른쪽 / 위쪽 / 왼쪽 / 아래쪽
while(nx >= 0 && nx < n && ny >= 0 && ny < m) {
//6인 경우, 거기까지 break하고 재귀로 다음 cctv를 탐색한다
if( map[nx][ny] == 6) break;
//혹시 CCTV 자리거나 이미 방문한 곳이라면 지나간다.
if( map[nx][ny] == 0 && vis[nx][ny] == false) {
tmpMaxCnt++;
vis[nx][ny] = true;
tmpVisited.add(new Point(nx, ny));
}
nx += dx[i];
ny += dy[i];
}
//두번째 방향
//위쪽 / 왼쪽 / 아래쪽 / 오른쪽
nx = tmpX+dx[(i+1)%4]; //다시 방향 맞춰서 초기화
ny = tmpY+dy[(i+1)%4];
while(nx >= 0 && nx < n && ny >= 0 && ny < m) {
//6인 경우, 거기까지 break하고 재귀로 다음 cctv를 탐색한다
if( map[nx][ny] == 6) break;
//혹시 CCTV 자리거나 이미 방문한 곳이라면 지나간다.
if( map[nx][ny] == 0 && vis[nx][ny] == false) {
tmpMaxCnt++;
vis[nx][ny] = true;
tmpVisited.add(new Point(nx, ny));
}
nx += dx[(i+1)%4];
ny += dy[(i+1)%4];
}
recur(cctvIdx+1);
//원상복귀
tmpMaxCnt -= tmpVisited.size();
for(Point p : tmpVisited) {
vis[p.x][p.y]= false;
}
}
break;
case 4:
for(int i = 0; i < 4; i++) { //4가지 방향-> 오른쪽과 위쪽과 왼쪽 / 위쪽과 왼쪽과 아래쪽
//왼쪽과 아래쪽과 오른쪽 / 아래쪽과 오른쪽과 위쪽
int nx = tmpX+dx[i];
int ny = tmpY+dy[i];
//이번 방향에 대해서 방문한 점들을 모두 저장하고 나중에 재귀가 돌아왔을때, 다시 원복해준다.
ArrayList<Point> tmpVisited = new ArrayList<>();
//총 세방향 확인 : 첫번째 방향
//오른쪽 / 위쪽 / 왼쪽 / 아래쪽
while(nx >= 0 && nx < n && ny >= 0 && ny < m) {
//6인 경우, 거기까지 break하고 재귀로 다음 cctv를 탐색한다
if( map[nx][ny] == 6) break;
//혹시 CCTV 자리거나 이미 방문한 곳이라면 지나간다.
if( map[nx][ny] == 0 && vis[nx][ny] == false) {
tmpMaxCnt++;
vis[nx][ny] = true;
tmpVisited.add(new Point(nx, ny));
}
nx += dx[i];
ny += dy[i];
}
//두번째 방향
//위쪽 / 왼쪽 / 아래쪽 / 오른쪽
nx = tmpX+dx[(i+1)%4]; //다시 방향 맞춰서 초기화
ny = tmpY+dy[(i+1)%4];
while(nx >= 0 && nx < n && ny >= 0 && ny < m) {
//6인 경우, 거기까지 break하고 재귀로 다음 cctv를 탐색한다
if( map[nx][ny] == 6) break;
//혹시 CCTV 자리거나 이미 방문한 곳이라면 지나간다.
if( map[nx][ny] == 0 && vis[nx][ny] == false) {
tmpMaxCnt++;
vis[nx][ny] = true;
tmpVisited.add(new Point(nx, ny));
}
nx += dx[(i+1)%4];
ny += dy[(i+1)%4];
}
//세번째 방향
//왼쪽 / 아래쪽 / 오른쪽 / 위쪽
nx = tmpX+dx[(i+2)%4]; //다시 방향 맞춰서 초기화
ny = tmpY+dy[(i+2)%4];
while(nx >= 0 && nx < n && ny >= 0 && ny < m) {
//6인 경우, 거기까지 break하고 재귀로 다음 cctv를 탐색한다
if( map[nx][ny] == 6) break;
//혹시 CCTV 자리거나 이미 방문한 곳이라면 지나간다.
if( map[nx][ny] == 0 && vis[nx][ny] == false) {
tmpMaxCnt++;
vis[nx][ny] = true;
tmpVisited.add(new Point(nx, ny));
}
nx += dx[(i+2)%4];
ny += dy[(i+2)%4];
}
recur(cctvIdx+1);
//원상복귀
tmpMaxCnt -= tmpVisited.size();
for(Point p : tmpVisited) {
vis[p.x][p.y]= false;
}
}
break;
case 5:
//이번 방향에 대해서 방문한 점들을 모두 저장하고 나중에 재귀가 돌아왔을때, 다시 원복해준다.
ArrayList<Point> tmpVisited = new ArrayList<>();
for(int i = 0; i < 4; i++) { //4가지 방향
int nx = tmpX+dx[i];
int ny = tmpY+dy[i];
while(nx >= 0 && nx < n && ny >= 0 && ny < m) {
//6인 경우, 거기까지 break하고 재귀로 다음 cctv를 탐색한다
if( map[nx][ny] == 6) break;
//혹시 CCTV 자리거나 이미 방문한 곳이라면 지나간다.
if( map[nx][ny] == 0 && vis[nx][ny] == false) {
tmpMaxCnt++;
vis[nx][ny] = true;
tmpVisited.add(new Point(nx, ny));
}
nx += dx[i];
ny += dy[i];
}
}
recur(cctvIdx+1);
//원상복귀
tmpMaxCnt -= tmpVisited.size();
for(Point p : tmpVisited) {
vis[p.x][p.y]= false;
}
break;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt(); //행
m = sc.nextInt(); //열
map = new int[n][m];
vis = new boolean[n][m];
maxCnt = 0; //cctv영역에 들어올 수 있는 0의 최대값
tmpMaxCnt = 0; //최대값을 갱신할 임시변수
zeroCnt = 0; //map의 총 0의 개수 저장
ans = 0;//사각지대의 최소값
list = new ArrayList<>();
for(int i = 0; i < n; i ++) {
for(int j = 0; j < m; j ++) {
vis[i][j] = false;
map[i][j] = sc.nextInt();
//0의 개수를 구하고 cctv영역에 들어온 0의 최대값(maxCnt)을 빼면 사각지대의 최소값이 나온다.
if(map[i][j] == 0) zeroCnt++;
//입력받으면서 cctv의 위치를 저장
if(map[i][j] != 0 && map[i][j] != 6) { //cctv 위치 저장
list.add(new Point(i, j));
}
}
}
recur(0);
ans = zeroCnt - maxCnt;
System.out.println(ans);
}
}
다른 풀이 코드
👀 한 방향의 방문배열을 만들지 않고 방문맵을 매개변수로 받아서 방향을 바꿀 때마다 그 매개변수 방문맵을 하드 카피해서 사용한다.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
//CCTV 클래스
class CCTV {
int x,y; //CCTV 위치
int type; //CCTV 유형
public CCTV(int x, int y, int type) {
this.x = x;
this.y = y;
this.type = type;
}
}
public class Main_15683 {
static int N;
static int M;
static int[][] map;
static ArrayList<CCTV> list = new ArrayList<>();
static int result = Integer.MAX_VALUE;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
map = new int[N][M];
for(int i = 0 ; i < N; i++) {
for(int j = 0; j < M; j++) {
map[i][j] = sc.nextInt();
if(map[i][j] >= 1 && map[i][j] <= 5) {
list.add(new CCTV(j, i, map[i][j])); // 현재 CCTV 리스트 만들기
}
}
}
dfs(0, map);
System.out.println(result);
}
/**
*
* @param idx : 현재보는 CCTV index
* @param prev : CCTV 감시가 기록된 배열
*/
static void dfs(int idx, int[][] prev) {
int[][] v = new int[N][M]; //임시 배열 선언
//기저 조건 - 모든 CCTV 방향이 결정 된 경우
if(idx == list.size()) {
int cnt = 0;
// 사각지대 개수 카운팅
for(int i = 0; i < N; i++) {
for(int j = 0 ; j < M; j++) {
if(prev[i][j] == 0) {
cnt++;
}
}
}
//결과의 최솟값 갱신
result = Math.min(result, cnt);
return;
}
// CCTV 가져와서 방향 결정하기
CCTV cctv = list.get(idx); //리스트에서 해당 CCTV 가져오기
int x = cctv.x;
int y = cctv.y;
switch(cctv.type) { // 몇번 CCTV인 확인
case 1 : // 4방향으로 회전가능, 모두 검사(상, 하, 좌, 우)
for(int d = 0 ; d < 4; d++) {
//전달받은 맵 임시 맵으로 하드카피
for(int i = 0; i < N; i++) {
v[i] = Arrays.copyOf(prev[i], M);
//방향을 바꿀 때마다 이전의 방문맵으로 바꾼다.(하드카피)
}
//CCTV 감시 범위 체크 (한방향)
detect(v, x, y, d);
dfs(idx+1, v); // 다음 CCTV 방향 결정을 위해 재귀 호출
}
break;
case 2 : //2방향 최전하면서 모두 검사(상하, 좌우)
for(int d = 0 ; d < 2; d++) {
for(int i = 0; i < N; i++) {
v[i] = Arrays.copyOf(prev[i], M);
}
//한번에 2방향 보기 때문에 메소드 2개 호출 0-2, 1-3tpxm
detect(v, x, y, d);
detect(v, x, y, d+2);
//임시 맵에 CCTV 체크 완료 했으면, dfs로 다음 CCTV 재귀 호출
dfs(idx+1, v);
}
break;
case 3 : // 직각으로 감시 - 4가지 버전
for(int d = 0 ; d < 4; d++) {
for(int i = 0; i < N; i++) {
v[i] = Arrays.copyOf(prev[i], M);
}
// 지각으로 2개 방향 검사하기 때문에 2개 메소드 호출, 90도 직각 반영? 나머지 연산을 통해서 구현
detect(v, x, y, d);
detect(v, x, y, (d+1) %4);
//dfs 재귀 호출
dfs(idx+1, v);
}
break;
case 4 : //3방향 보기
for(int d = 0 ; d < 4; d++) {
for(int i = 0; i < N; i++) {
v[i] = Arrays.copyOf(prev[i], M);
}
//3개 방향 감시하기 때문에 3개 메소드 호출, 90도, 180도 반영을 위한 나머지 연산
detect(v, x, y, d);
detect(v, x, y, (d+1) %4);
detect(v, x, y, (d+2) %4);
dfs(idx+1, v);
}
break;
case 5 :
for(int d = 0 ; d < 4; d++) {
for(int i = 0; i < N; i++) {
v[i] = Arrays.copyOf(prev[i], M);
}
detect(v, x, y, 0);
detect(v, x, y, 1);
detect(v, x, y, 2);
detect(v, x, y, 3);
dfs(idx+1, v);
}
break;
}
}
/**
*
* @param vMap : 체크할 배열 정보
* @param x : CCTV 위치
* @param y
* @param dir : CCTV 방향
*/
static void detect(int[][] vMap, int x, int y, int dir) {
switch(dir) {
// dir 0: 좌, 1: 상, 2: 우, 3: 하
case 0 :
for(int i = x; i >= 0; i--) {
if(vMap[y][i] == 6) {
break;
}
vMap[y][i] = 9; //감시하는 부분은 다른 값으로 셋팅
}
break;
case 1 :
for(int i = y; i >= 0; i--) {
if(vMap[i][x] == 6) {
break;
}
vMap[i][x] = 9;
}
break;
case 2 :
for(int i = x; i < M; i++) {
if(vMap[y][i] == 6) {
break;
}
vMap[y][i] = 9;
}
break;
case 3 :
for(int i = y; i < N; i++) {
if(vMap[i][x] == 6) {
break;
}
vMap[i][x] = 9;
}
break;
}
}
}
바른 자세로 코딩합니다 👦🏻💻