[백준] 15683번 : 감시

문제

 

 

접근 방식

바킹독님 시뮬레이션 강의를 들으면서 처음 풀어보는 빡구현 문제로

지문 길이 보고 풀기 싫어지지만 귀찮음을 이겨내고 풀어냈다...

 

무식하게 풀다 보니 코드가 엄청 길어지긴 했지만 백트래킹을 사용해서

쉽게 풀 수 있는 문제다. (지문의 길이게 겁먹지 말자...)

 

백트래킹 연습 문제로 풀었던 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;
		}
	}
}