[BOJ] 15683번: 감시

역시 dfs 코드생각하는일은 넘 힘들다...난 dfs바보...

---

문제가 길기 때문에 생략하겠습니당ㅇㅅㅇ

 

🔍나의 풀이

처음 생각한 큰 풀이 방향은 모든 경우에 대해서 사각지대 크기를 체크하고 최솟 값을 찾아주면 된다.

 

1. 입력된 사무실 정보를 저장, 저장하면서 카메라 정보(카메라 종류, 위치)도 같이 저장
2. 카메라 종류는 5가지, 카메라가 90도씩 회전했을 때의 감시 방향이 달라지는 경우도 체크
   • 1,3,4번 카메라는 회전에 따라 4가지 상황이 생김
   • 2번 카메라는 2가지
   • 5번 카메라는 모든 방향을 감시 중이므로 회전해도 동일(회전을 고려하지 않아도 됨)
3. 사무실과 동일한 크기로 만든 임시 이차원 배열에 감시할 수 있는 영역을 7로 변경
   (벽과 사무실의 끝을 체크해줘야 함)
4. 모든 카메라에 대한 감시 영역 체크를 끝내고 주어진 사각 지대의 최소 크기를 출력

✔️ 내 코드

package BOJ;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Surveillance {
    static int N, M, min = Integer.MAX_VALUE;
    static int[][] room;
    static int camCnt;
    static ArrayList<Camera> camlist =  new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();

        room = new int[N][M];
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                int v = sc.nextInt();
                if(v!=0 && v!=6){
                    camlist.add(new Camera(i, j, v));
                }
                room[i][j] = v;
            }
        }
        camCnt = camlist.size();

        allCamera(0, room);
        System.out.println(min);
    }
    
    static void allCamera(int idx, int[][] room){
        int[][] tmpRoom = new int[N][M];
        if(idx==camCnt){
            int zeroCnt = 0;
            for(int i=0; i<N; i++){
                for(int j=0; j<M; j++){
                    if(room[i][j]==0){
                        zeroCnt++;
                    }
                }
            }
            if(zeroCnt<min){
                min = zeroCnt;
            }
        } else {
            Camera cam = camlist.get(idx);
            
            switch (cam.num) {  // 카메라 타입에 따라 회전 횟수 다르게 가능
                case 1:
                    for (int dir = 0; dir < 4; dir++) {
                        for (int i = 0; i < N; i++) {
                            tmpRoom[i] = Arrays.copyOf(room[i], M);
                        }
                        check(tmpRoom, cam.posX, cam.posY, dir);
                        allCamera(idx + 1, tmpRoom);
                    }
                    break;
                case 2:
                    for (int dir = 0; dir < 2; dir++) {
                        for (int i = 0; i < N; i++) {
                            tmpRoom[i] = Arrays.copyOf(room[i], M);
                        }
                        check(tmpRoom, cam.posX, cam.posY, dir);
                        check(tmpRoom, cam.posX, cam.posY, (dir + 2) % 4);
                        allCamera(idx + 1, tmpRoom);
                    }
                    break;
                case 3:
                    for (int dir = 0; dir < 4; dir++) {
                        for (int i = 0; i < N; i++) {
                            tmpRoom[i] = Arrays.copyOf(room[i], M);
                        }
                        check(tmpRoom, cam.posX, cam.posY, dir);
                        check(tmpRoom, cam.posX, cam.posY, (dir + 1) % 4);
                        allCamera(idx + 1, tmpRoom);
                    }
                    break;
                case 4:
                    for (int dir = 0; dir < 4; dir++) {
                        for (int i = 0; i < N; i++) {
                            tmpRoom[i] = Arrays.copyOf(room[i], M);
                        }
                        check(tmpRoom, cam.posX, cam.posY, dir);
                        check(tmpRoom, cam.posX, cam.posY, (dir + 1) % 4);
                        check(tmpRoom, cam.posX, cam.posY, (dir + 2) % 4);
                        allCamera(idx + 1, tmpRoom);
                    }
                    break;
                case 5:
                    for (int i = 0; i < N; i++) {
                        tmpRoom[i] = Arrays.copyOf(room[i], M);
                    }
                    check(tmpRoom, cam.posX, cam.posY, 0);
                    check(tmpRoom, cam.posX, cam.posY, 1);
                    check(tmpRoom, cam.posX, cam.posY, 2);
                    check(tmpRoom, cam.posX, cam.posY, 3);
                    allCamera(idx + 1, tmpRoom);
                    break;
            }
        }
    }
    
    // 카메라가 볼 수 있는 구간 체크
    static void check(int[][] tmpRoom, int i, int j, int dir){
        switch (dir){
            case 0:
                for (int k = j; k >= 0; k--) {
                    if (room[i][k] == 6) {
                        break;
                    }
                    tmpRoom[i][k] = 7;
                }
                break;
            case 1:
                for (int k = i; k >= 0; k--) {
                    if (room[k][j] == 6) {
                        break;
                    }
                    tmpRoom[k][j] = 7;
                }
                break;
            case 2:
                for (int k = j; k < M; k++) {
                    if (room[i][k] == 6) {
                        break;
                    }
                    tmpRoom[i][k] = 7;
                }
                break;
            case 3:
                for (int k = i; k < N; k++) {
                    if (room[k][j] == 6) {
                        break;
                    }
                    tmpRoom[k][j] = 7;
                }
                break;
        }
    }
}

class Camera{
    int posX;
    int posY;
    int num;

    Camera(int posX, int posY, int num){
        this.posX = posX;
        this.posY = posY;
        this.num = num;
    }
}

---

문제 출처: https://www.acmicpc.net/problem/15683

15683번: 감시