문제
접근 방식
바킹독님 시뮬레이션 강의를 들으면서 처음 풀어보는 빡구현 문제로
지문 길이 보고 풀기 싫어지지만 귀찮음을 이겨내고 풀어냈다...
무식하게 풀다 보니 코드가 엄청 길어지긴 했지만 백트래킹을 사용해서
쉽게 풀 수 있는 문제다. (지문의 길이게 겁먹지 말자...)
백트래킹 연습 문제로 풀었던 N과 M 시리즈를 CCTV에 적용하면 되는 문제로
1번 : 위, 오른쪽, 아래, 왼쪽 중 한 방향이벽을 만나기 전까지 감시 가능
2번 : 위/아래, 왼쪽/오른쪽 중 양쪽이 벽을 만나기 전까지 감시 가능
3번 : 위/오른쪽, 오른쪽/아래, 아래/왼쪽, 왼쪽/위처럼 직각인 두 방향이 벽을 만나기 전까지 감시 가능
4번 : 위/오른쪽/아래, 오른쪽/아래/왼쪽, 아래/왼쪽/위, 왼쪽/위/오른쪽처럼 세 방향이 벽을 만나기 전까지 감시 가능
5번 : 위/오른쪽/아래/왼쪽이 모두 벽을 만나기 전까지 감시 가능
위와 같이 CCTV 종류 별로 감시 가능한 경우의 수들을 모두 시도해 주면 된다.
사각지대는 경우의 수들을 모두 시도해 보며 마지막 CCTV를 방문했을 때
현재까지 방문하지 않은 곳 + 벽의 수를 구하면 알 수 있기 때문에
테스트 케이스를 입력을 받으면서 CCTV의 좌표를 리스트에 저장해 둔 후에
리스트를 이용해 백트래킹을 해주면서 방문 여부를 체크해 준다.
이때 조심해야 할 부분은 백트래킹에서 다른 cctv가 감시한 부분의 방문 여부를
다른 cctv가 바꿀 수 없게 해야 한다.
// 초기 상태
4 0 0 0 0 0 0
0 0 0 2 0 0 0
0 0 0 0 0 0 4
// 방문 후
4 x x x x x x
x 0 0 2 0 0 x
x x x x x x 4
// 잘못된 케이스
4 x x x x x 0
x 0 0 2 0 0 0
x 0 0 0 0 0 4
// 다른 CCTV에 관여하지 말아야 함
4 x x x x x x
x 0 0 2 0 0 0
x 0 0 x 0 0 4
즉, 위와 같이 다른 CCTV가 먼저 감시 중인 곳을 건드리면 안된다.
이 부분을 해결하기 위해 방문여부를 boolean 배열이 아닌
몇 번째 CCTV인지 리스트의 인덱스를 사용해서 기록했다.
풀이
public class Main {
private static int n;
private static int m;
private static int size;
private static int min = Integer.MAX_VALUE;
private static int[][] office;
private static int[][] isWatched;
private static List<CCTV> cctvs;
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());
office = new int[n][m];
isWatched = new int[n][m];
cctvs = new ArrayList<>();
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
int num = Integer.parseInt(st.nextToken());
office[i][j] = num;
if (num == 6) isWatched[i][j] = 1;
else if (num != 0) {
cctvs.add(new CCTV(i, j));
}
}
}
size = cctvs.size();
watch(0);
System.out.println(min);
}
private static void watch(int idx) {
if (idx == size) {
int count = 0;
for (int[] w : isWatched) {
for (int b : w) {
if (b == 0) count++;
}
}
min = Math.min(min, count);
return;
}
CCTV cur = cctvs.get(idx);
int x = cur.x;
int y = cur.y;
int cctv = office[x][y];
switch (cctv) {
case 1: {
up(idx, x, y);
down(idx, x, y);
left(idx, y, x);
right(idx, y, x);
break;
}
case 2: {
height(idx, x, y);
width(idx, y, x);
break;
}
case 3: {
upRight(idx, x, y);
rightDown(idx, x, y);
downLeft(idx, x, y);
leftUp(idx, x, y);
break;
}
case 4: {
leftUpRight(idx, x, y);
upRightDown(idx, x, y);
rightDownLeft(idx, x, y);
downLeftUp(idx, x, y);
break;
}
case 5: {
all(idx, x, y);
break;
}
}
}
private static void right(int idx, int y, int x) {
visitRigth(idx, y, x);
watch(idx + 1);
rollbackRight(idx, y, x);
}
private static void rollbackRight(int idx, int y, int x) {
for (int j = y; j < m; j++) {
if (office[x][j] == 6) break;
if (isWatched[x][j] != idx + 1) continue;
isWatched[x][j] = 0;
}
}
private static void visitRigth(int idx, int y, int x) {
for (int j = y; j < m; j++) {
if (office[x][j] == 6) break;
if (isWatched[x][j] != 0) continue;
isWatched[x][j] = idx + 1;
}
}
private static void left(int idx, int y, int x) {
visitLeft(idx, y, x);
watch(idx + 1);
rollbackLeft(idx, y, x);
}
private static void rollbackLeft(int idx, int y, int x) {
for (int j = y; j >= 0; j--) {
if (office[x][j] == 6) break;
if (isWatched[x][j] != idx + 1) continue;
isWatched[x][j] = 0;
}
}
private static void visitLeft(int idx, int y, int x) {
for (int j = y; j >= 0; j--) {
if (office[x][j] == 6) break;
if (isWatched[x][j] != 0) continue;
isWatched[x][j] = idx + 1;
}
}
private static void down(int idx, int x, int y) {
visitDown(idx, x, y);
watch(idx + 1);
rollbackDown(idx, x, y);
}
private static void rollbackDown(int idx, int x, int y) {
for (int j = x; j < n; j++) {
if (office[j][y] == 6) break;
if (isWatched[j][y] != idx + 1) continue;
isWatched[j][y] = 0;
}
}
private static void visitDown(int idx, int x, int y) {
for (int j = x; j < n; j++) {
if (office[j][y] == 6) break;
if (isWatched[j][y] != 0) continue;
isWatched[j][y] = idx + 1;
}
}
private static void up(int idx, int x, int y) {
visitUp(idx, x, y);
watch(idx + 1);
rollbackUp(idx, x, y);
}
private static void rollbackUp(int idx, int x, int y) {
for (int j = x; j >= 0; j--) {
if (office[j][y] == 6) break;
if (isWatched[j][y] != idx + 1) continue;
isWatched[j][y] = 0;
}
}
private static void visitUp(int idx, int x, int y) {
for (int j = x; j >= 0; j--) {
if (office[j][y] == 6) break;
if (isWatched[j][y] != 0) continue;
isWatched[j][y] = idx + 1;
}
}
private static void all(int idx, int x, int y) {
visitLeft(idx, y, x);
visitUp(idx, x, y);
visitRigth(idx, y, x);
visitDown(idx, x, y);
watch(idx + 1);
rollbackLeft(idx, y, x);
rollbackUp(idx, x, y);
rollbackRight(idx, y, x);
rollbackDown(idx, x, y);
}
private static void leftUpRight(int idx, int x, int y) {
visitLeft(idx, y, x);
visitUp(idx, x, y);
visitRigth(idx, y, x);
watch(idx + 1);
rollbackLeft(idx, y, x);
rollbackUp(idx, x, y);
rollbackRight(idx, y, x);
}
private static void upRightDown(int idx, int x, int y) {
visitUp(idx, x, y);
visitRigth(idx, y, x);
visitDown(idx, x, y);
watch(idx + 1);
rollbackUp(idx, x, y);
rollbackRight(idx, y, x);
rollbackDown(idx, x, y);
}
private static void rightDownLeft(int idx, int x, int y) {
visitRigth(idx, y, x);
visitDown(idx, x, y);
visitLeft(idx, y, x);
watch(idx + 1);
rollbackRight(idx, y, x);
rollbackDown(idx, x, y);
rollbackLeft(idx, y, x);
}
private static void downLeftUp(int idx, int x, int y) {
visitDown(idx, x, y);
visitLeft(idx, y, x);
visitUp(idx, x, y);
watch(idx + 1);
rollbackDown(idx, x, y);
rollbackLeft(idx, y, x);
rollbackUp(idx, x, y);
}
private static void width(int idx, int y, int x) {
visitRigth(idx, y, x);
visitLeft(idx, y, x);
watch(idx + 1);
rollbackRight(idx, y, x);
rollbackLeft(idx, y, x);
}
private static void height(int idx, int x, int y) {
visitUp(idx, x, y);
visitDown(idx, x, y);
watch(idx + 1);
rollbackUp(idx, x, y);
rollbackDown(idx, x, y);
}
private static void upRight(int idx, int x, int y) {
visitUp(idx, x, y);
visitRigth(idx, y, x);
watch(idx + 1);
rollbackUp(idx, x, y);
rollbackRight(idx, y, x);
}
private static void rightDown(int idx, int x, int y) {
visitRigth(idx, y, x);
visitDown(idx, x, y);
watch(idx + 1);
rollbackRight(idx, y, x);
rollbackDown(idx, x, y);
}
private static void downLeft(int idx, int x, int y) {
visitDown(idx, x, y);
visitLeft(idx, y, x);
watch(idx + 1);
rollbackDown(idx, x, y);
rollbackLeft(idx, y, x);
}
private static void leftUp(int idx, int x, int y) {
visitLeft(idx, y, x);
visitUp(idx, x, y);
watch(idx + 1);
rollbackLeft(idx, y, x);
rollbackUp(idx, x, y);
}
private static class CCTV {
int x;
int y;
public CCTV(int x, int y) {
this.x = x;
this.y = y;
}
}
}
'Java > Algorithms' 카테고리의 다른 글
[백준] 20166번 : 문자열 지옥에 빠진 호석 (0) | 2023.12.15 |
---|---|
[백준] 1463번 : 1로 만들기 (0) | 2023.12.11 |
[백준] 1725번 : 히스토그램 (0) | 2023.11.16 |
[백준] 7795번 : 먹을 것인가 먹힐 것인가 (1) | 2023.11.16 |
[백준] 2910번 : 빈도 정렬 (1) | 2023.11.16 |