문제
문제 설명
최대 8 X 8 크기의 격자 내에 1번부터 5번 종류의 CCTV의 위치와 벽의 정보가 주어진다.
이 상황에서 각 위치에 있는 CCTV 들을 회전할 수 있을 때 감시 사각 지대의 최소 크기를 구하는 문제이다.
구현
일단 혼자 생각하다가 바킹독님의 시뮬레이션 강의를 참고해서 풀었다.
내가 혼자 생각한거는 일단 입력 받으면 CCTV의 좌표들을 저장해두고 최근에 비트마스킹을 풀어서 그런지 이번에도 그렇게 풀면 되지 않을까? 라는 생각을 했다.
각 CCTV가 가질 수 있는 최대의 상태는 4개니깐 최대 CCTV 개수인 4^8 이라고 해봤자 대충 60,000 쯤이여서 풀릴거같긴 했는데 비트마스킹이 아니라 4진수를 사용해야 되는 데에서 구현 방향이나 이게 맞는지 확신이 들지 않아서 강의를 봤는데 이렇게 푸는게 맞았다.
일단 전체적으로 짠 흐름은 아래와 같다.
- CCTV의 좌표를 담는다.
- 각 CCTV가 가질 수 있는 상태를 4진수로 체크한다.
- 그 후 CCTV의 상태에 따라 감시 사각지대의 넓이를 구한다.
이렇게 순서대로 구현을 하면 된다.
일단 감시카메라를 담는 배열로는 Camera 라는 클래스를 선언하고 좌표를 저장하게 하고 그 Camera를 담는 ArrayList 를 선언해주어 감시카메라 배열을 만들어주었다.
for(int i = 0; i < n; i++){
st = new StringTokenizer(br.readLine());
for(int j = 0; j < m; j++){
arr[i][j] = Integer.parseInt(st.nextToken());
//CCTV 인경우
if (arr[i][j] != 0 && arr[i][j] != 6) {
cctvList.add(new Camera(i, j));
}
}
}그리고 이제 모든 경우의 수를 확인해야 한다.
각 CCTV 별로 4개의 상태를 가질 수 있으니 위에서 저장해둔 cctvList의 크기를 4제곱한만큼의 경우의 수가 존재한다.
for(int mask = 0; mask < (1 << (2 * cctvList.size())); mask++) {
// 구현
}이렇게 되면 mask를 4진수로 변환한다면 각 CCTV의 상태가 0부터 3까지 주어지게 된다.
각 경우의 수 별로 감시 사각 구역을 확인해주어야 하기 때문에 arr를 tempArr 에 복사를 떠놓은 후 시작한다.
for(int mask = 0; mask < (1 << (2 * cctvList.size())); mask++) {
// 구현
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
tempArr[i][j] = arr[i][j];
}
}
}그 후에는 이제 CCTV 들에게 방향을 정해줄 차례이다.
현재 주어진 mask의 값을 임시로 저장해 둔 후 4진수로 변환하여 현재 cctvList 에 순서대로 방향을 지정해주면 된다.
그 후에 그 CCTV가 몇번 CCTV 인지 확인을 한 후 감시 가능한 구역을 체크해주면 된다.
//모든 경우의 수를 확인 -> CCTV의 개수별로 4진수가 정해짐
for (int mask = 0; mask < (1 << (2 * cctvList.size())); mask++) {
//배열 복사
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
tempArr[i][j] = arr[i][j];
}
}
int temp = mask;
for (int i = 0; i < cctvList.size(); i++) {
int dir = temp % 4;
temp /= 4;
//i 번째 CCTV의 좌표를 가져와서 무슨 CCTV 인지 확인
int x = cctvList.get(i).x;
int y = cctvList.get(i).y;
//CCTV 감시범위 체크
switch(arr[x][y]) {
//한쪽 방향
case 1:
watch(x, y, dir);
break;
//양쪽방향
case 2:
watch(x, y, dir);
watch(x, y, dir + 2);
break;
//ㄱ자 방향
case 3:
watch(x, y, dir);
watch(x, y, dir + 1);
break;
//세방향
case 4:
watch(x, y, dir);
watch(x, y, dir + 1);
watch(x, y, dir + 2);
break;
//전방향
case 5:
watch(x, y, dir);
watch(x, y, dir + 1);
watch(x, y, dir + 2);
watch(x, y, dir + 3);
break;
}
}
} 여기서의 watch 함수는 위에서 말했던 감시 가능한 구역을 체크해주는 함수이다.
넘겨주는 x 좌표와 y 좌표는 각각 CCTV의 현재 위치를 뜻하고 dir 은 방향을 뜻한다. switch 문에서 기존에 0 ~ 3 이였던 dir에 덧셈을 해줘서 4를 넘어갈 가능성이 있으니 모듈러 연산을 통해 다시 원래대로 돌려준다.
public static void watch(int x, int y, int dir) {
//dir이 4를 넘어갈 가능성이 있음
dir %= 4;
//구현
}그 후에는 정해진 dir 로 한칸씩 이동해주면서 격자를 벗어났거나 벽에 부딪히면 return 해주고
0이 아니라면 계속 continue 해주고 기본적으로는 다 방문했다는 표시인 7로 바꿔주면 된다.
public static void watch(int x, int y, int dir) {
//dir이 4를 넘어갈 가능성이 있음
dir %= 4;
while (true) {
x += dx[dir];
y += dy[dir];
//격자를 벗어났거나 벽에 부딪히면
if (x < 0 || x >= n || y < 0 || y >= m || arr[x][y] == 6) {
return;
}
//0이 아니면 다음곳으로 이동
if (tempArr[x][y] != 0) {
continue;
}
tempArr[x][y] = 7;
}
}이렇게 한 후 메인 함수에서 사각지대를 세서 최신화 해주면 되는 문제이다.
코드
import java.util.*;
import java.io.*;
public class Main_15683 {
static class Camera{
int x;
int y;
public Camera(int x, int y) {
this.x = x;
this.y = y;
}
}
static int n, m;
static int[][] arr;
static int answer = Integer.MAX_VALUE;
static int[][] tempArr;
static ArrayList<Camera> cctvList;
static int[] dx = {1, 0, -1, 0};
static int[] dy = {0, 1, 0, -1};
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());
arr = new int[n][m];
tempArr = new int[n][m];
cctvList = new ArrayList<>();
for(int i = 0; i < n; i++){
st = new StringTokenizer(br.readLine());
for(int j = 0; j < m; j++){
arr[i][j] = Integer.parseInt(st.nextToken());
//CCTV 인경우
if (arr[i][j] != 0 && arr[i][j] != 6) {
cctvList.add(new Camera(i, j));
}
}
}
//모든 경우의 수를 확인 -> CCTV의 개수별로 4진수가 정해짐
for (int mask = 0; mask < (1 << (2 * cctvList.size())); mask++) {
//배열 복사
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
tempArr[i][j] = arr[i][j];
}
}
int temp = mask;
for (int i = 0; i < cctvList.size(); i++) {
int dir = temp % 4;
temp /= 4;
//i 번째 CCTV의 좌표를 가져와서 무슨 CCTV 인지 확인
int x = cctvList.get(i).x;
int y = cctvList.get(i).y;
//CCTV 감시범위 체크
switch(arr[x][y]) {
//한쪽 방향
case 1:
watch(x, y, dir);
break;
//양쪽방향
case 2:
watch(x, y, dir);
watch(x, y, dir + 2);
break;
//ㄱ자 방향
case 3:
watch(x, y, dir);
watch(x, y, dir + 1);
break;
//세방향
case 4:
watch(x, y, dir);
watch(x, y, dir + 1);
watch(x, y, dir + 2);
break;
//전방향
case 5:
watch(x, y, dir);
watch(x, y, dir + 1);
watch(x, y, dir + 2);
watch(x, y, dir + 3);
break;
}
}
//사각지대 카운트해주기
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (tempArr[i][j] == 0) {
count++;
}
}
}
answer = Math.min(answer, count);
}
System.out.println(answer);
}
public static void watch(int x, int y, int dir) {
//dir이 4를 넘어갈 가능성이 있음
dir %= 4;
while (true) {
x += dx[dir];
y += dy[dir];
//격자를 벗어났거나 벽에 부딪히면
if (x < 0 || x >= n || y < 0 || y >= m || arr[x][y] == 6) {
return;
}
//0이 아니면 다음곳으로 이동
if (tempArr[x][y] != 0) {
continue;
}
tempArr[x][y] = 7;
}
}
}
