알고리즘/백준
15683_감시
베리영young
2024. 8. 20. 22:11
사용 알고리즘: 빡구현, 순조부, dfs
사용 언어: java
cctv를 한꺼번에 처리하는 방법이 없을까? 고민했지만 그런 건 없는 거 같다ㅎㅎ 그리하여 시작된 빡!구현..
사각지대 없애는 건 모듈화해서 재활용하려고 했다(remove~ 이름의 메서드들)
5번 cctv는 방향이 의미가 없으므로 맨처음에 먼저 동작시키고, 나머지 cctv의 방향을 정했다.
package ssafyAlgorithm;
import java.io.*;
import java.util.*;
public class Main_bj_15683_감시 {
static int n,m, map[][];
static ArrayList<int[]>[] cctv = new ArrayList[6];
static int[][] dir;
static int ans = Integer.MAX_VALUE;
public static void main(String[] args) {
input_15683();
//5번 cctv는 먼저 동작 => 사각지대가 아닌 곳은 -1
for(int[] cctv5 : cctv[5]) {
map = cctv5(cctv5, map);
}
//순열(순서 중요)로 cctv방향 정하기
permutation(1, 0); //1번 cctv
System.out.println(ans);
}
private static void permutation(int cctvNum, int cctvOrder) {
if(cctvNum >= 5) {
//cctv작동하기
int[][] copyMap = copy(map);
ans = Math.min(ans, operate(copyMap));
return;
}
if (cctv[cctvNum].size() > cctvOrder) {
for (int d = 0; d < 4; d++) {
dir[cctvNum][cctvOrder] = d;
permutation(cctvNum, cctvOrder + 1); // cctvOrder를 1 증가시켜 다음 방향으로 탐색
}
} else {
permutation(cctvNum + 1, 0); // 다음 CCTV로 이동
}
// if(cctv[cctvNum].size() == cctvOrder) {
// permutation(cctvNum+1, 0);
// }
//
// for(int d=0; d<4; d++) {
// dir[cctvNum][cctvOrder] = d;
// permutation(cctvNum, 1+cctvOrder);
// }
}
private static int operate(int[][] copyMap) {
//1~4번 cctv를 작동한 후,
for(int cctvNum=1; cctvNum<5; cctvNum++) {
for(int cctvOrder=0; cctvOrder<cctv[cctvNum].size(); cctvOrder++) {
copyMap = cctvOper(cctvNum, dir[cctvNum][cctvOrder], cctv[cctvNum].get(cctvOrder), copyMap);
}
}
//사각지대 개수 구하기(map에서 0인 부분)
int zero = 0;
for (int i = 0; i < n; i++) {
for(int j = 0; j<m; j++) {
if(copyMap[i][j] == 0) zero++;
}
}
return zero;
}
private static int[][] cctvOper(int cctvNum, int d, int[] xy, int[][] map) {
if(cctvNum==1) {
if(d==0) {
map = removeRight(xy[0], xy[1], map);
} else if(d==1) {
map = removeDown(xy[0], xy[1], map);
} else if(d==2) {
map = removeLeft(xy[0], xy[1], map);
} else {
map = removeUp(xy[0], xy[1], map);
}
} else if(cctvNum==2) {
if(d%2 == 0) {
map = removeRight(xy[0], xy[1], map);
map = removeLeft(xy[0], xy[1], map);
} else {
map = removeUp(xy[0], xy[1], map);
map = removeDown(xy[0], xy[1], map);
}
} else if(cctvNum==3) {
if(d==0) {
map = removeUp(xy[0], xy[1], map);
map = removeRight(xy[0], xy[1], map);
} else if(d==1) {
map = removeRight(xy[0], xy[1], map);
map = removeDown(xy[0], xy[1], map);
} else if(d==2) {
map = removeDown(xy[0], xy[1], map);
map = removeLeft(xy[0], xy[1], map);
} else {
map = removeLeft(xy[0], xy[1], map);
map = removeUp(xy[0], xy[1], map);
}
} else {
if(d==0) {
map = removeLeft(xy[0], xy[1], map);
map = removeUp(xy[0], xy[1], map);
map = removeRight(xy[0], xy[1], map);
} else if(d==1) {
map = removeUp(xy[0], xy[1], map);
map = removeRight(xy[0], xy[1], map);
map = removeDown(xy[0], xy[1], map);
} else if(d==2) {
map = removeRight(xy[0], xy[1], map);
map = removeDown(xy[0], xy[1], map);
map = removeLeft(xy[0], xy[1], map);
} else {
map = removeDown(xy[0], xy[1], map);
map = removeLeft(xy[0], xy[1], map);
map = removeUp(xy[0], xy[1], map);
}
}
return map;
}
private static int[][] copy(int[][] map2) {
int[][] mmap = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
mmap[i][j] = map2[i][j];
}
}
return mmap;
}
private static int[][] cctv5(int[] cctv5, int[][] map) {
int x = cctv5[0]; int y = cctv5[1];
//위
map = removeUp(x, y, map);
//아래
map = removeDown(x, y, map);
//왼
map = removeLeft(x, y, map);
//오른
map = removeRight(x, y, map);
return map;
}
private static int[][] removeRight(int x, int y, int[][] map) {
for (int j=y+1; j<m; j++) {
if(map[x][j] == 6) break;
map[x][j] = -1;
}
return map;
}
private static int[][] removeLeft(int x, int y, int[][] map) {
for (int j=y-1; j>=0; j--) {
if(map[x][j] == 6) break;
map[x][j] = -1;
}
return map;
}
private static int[][] removeDown(int x, int y, int[][] map) {
for(int i=x+1; i<n; i++) {
if(map[i][y] == 6) break;
map[i][y] = -1;
}
return map;
}
private static int[][] removeUp(int x, int y, int[][] map) {
for(int i=x-1; i>=0; i--) {
if(map[i][y] == 6) break;
map[i][y] = -1;
}
return map;
}
private static void input_15683() {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
map = new int[n][m];
dir = new int[5][]; //1~4까지 사용
for (int i = 0; i < 6; i++) {
//cctv는 인덱스 1부터 5까지
//{x위치, y위치, cctv방향}
cctv[i] = new ArrayList<>();
}
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) {
cctv[map[i][j]].add(new int[] {i,j});
}
}
}
for(int i=1; i<5; i++) {
dir[i] = new int[cctv[i].size()];
} //cctv의 방향 결정
}
}
여기서 문제가 됐던 부분은
private static void permutation(int cctvNum, int cctvOrder) {
if(cctvNum >= 5) {
//cctv작동하기
int[][] copyMap = copy(map);
ans = Math.min(ans, operate(copyMap));
// System.out.println("ans: "+ans);
return;
}
if (cctv[cctvNum].size() > cctvOrder) {
for (int d = 0; d < 4; d++) {
dir[cctvNum][cctvOrder] = d;
permutation(cctvNum, cctvOrder + 1); // cctvOrder를 1 증가시켜 다음 방향으로 탐색
}
} else {
permutation(cctvNum + 1, 0); // 다음 CCTV로 이동
}
// if(cctv[cctvNum].size() == cctvOrder) {
// permutation(cctvNum+1, 0);
// }
//
// for(int d=0; d<4; d++) {
// dir[cctvNum][cctvOrder] = d;
// permutation(cctvNum, 1+cctvOrder);
// }
}인데,
밑에 주석처리 한 곳처럼 하면, 한 바퀴를 돈 후 ArrayOutOfIndex인가 하는 에러가 생긴다.
그래서 사이즈보다, 현재 order가 작을 때 방향을 정하고, 그 외에는 다음 cctv로 넘어가게 바꾸니까 잘 동작한다.
이거나 저거나 동작 방법은 같은 거 아닌가??? 왜 주석처리 한 부분은 에러가 나는지 모르겠다.
길을 가다가 이 글을 보는 분은 답을 알려주시면 감사하겠습니다ㅎㅎ