[백준] 15683번 감시

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/swtest/Q15683.java

여러 형태의 CCTV가 존재한다. 각 CCTV는 아래와 같이 감시를 한다.
사무실에는 벽도 있다. 벽은 6으로 주어진다. CCTV는 벽을 넘어서는 감시할 수 없다.
CCTV는 벽을 넘어서 감시할 수 는 없으나 다른 CCTV를 넘어서는 감시 할 수 있다.
또 각 CCTV들은 90도씩 회전해서 다른 방향들을 감시 할 수 있다. 예를들어 4번을 보면
초기 감시가 ㅗ 였다면 ㅏ ㅜ ㅓ 형태의 감시도 회전을 통해 가능하다. 벽과 CCTV 들이 주어질 때,
감시 하지 못하는 사각지대 영역의 최소 크기를 구하여라.

처음 생각

회전이 없다면 각 CCTV가 바라보는 방향대로 맵에 표시를 해준 뒤, 사각 지대 즉 맵에서 0의 개수를 세면된다. 하지만 각 CCTV들은 90도 씩 회전이 가능하다. 

다음 생각

각 CCTV마다 90도 씩 회전할 때 생기는 경우의 수는 4가지다. 원 상태, 90도, 90+90도, 90+90+90도로 마지막에서 한 번더 90도를 돈다면 원 상태로 돌아오게된다.

▶ 저 4개의 상태를 0,1,2,3으로 생각해서 DFS 탐색을 통해 각 CCTV마다 돌리는 상태의 모든 조합을 만들어 준 뒤, 마지막 CCTV까지 상태가 결정되면 해당 방향들을 가지고 있을 때, 사각지대를 구하였다.

다다음 생각

우선, 1~5번의 CCTV가 다 제각각 이므로 하나로 합치기는 어렵다 생각하여 switch case 문으로 분리를 해주었다. 그 후 일반적인 BFS 탐색이 이용하는 상 하 좌 우 이동배열을 만들어서 이를 이용해 탐색을 하게하였다. 잠깐 코드를 통해 보면 다음과 같다.

// 우 하 좌 상
static int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};

위와 같이 방향 배열을 만들어 주었다. 시작이 우 하 좌 상 인 이유는 예제로 주어진 CCTV의 형태를 그대로 사용하기 위해서 였다. 

▶ 1번 CCTV의 예제 그림이 오른쪽을 바라보고 있으므로 우 로 시작해 주었다.

▶ 2번 CCTV의 예제는 들어온 방향 인덱스에 +2를 해주면 반대 방향을 체크할 수 있다. 이 때, dir의 index가 3이 끝이므로 2나 3에서 +2를 해줄 경우 앞쪽 0,1 index를 확인해야 하므로 더한 값의 %4를 통해 4를 넘어가더라도 0부터 돌도록 하였다. 

▶ 마찬가지로 3번 CCTV를 보면 상,우가 시작이다. 현 index에서 +1한 것을 해주면 계속 저런 모양이 유지된다. 따라서 들어온 방향 index와 +1 까지 방향을 살펴보도록 하였다. 이것도 +1의 경우 index 범위를 초과할 수 있으므로 %4를 통해 해결해 주었다.

▶ 4번 CCTV는 3방향을 살펴보면된다. 3번의 연장선으로 +1을 한 번 더해주면 연속된 3방향을 볼 수 있다.

▶ 5번 CCTV는 어떤 방향으로 들어오던 0~3까지 보든 방향을 다 봐주었다.

다다다음 생각

방향 탐색을 위한 일반적인 BFS 탐색을 생각해보면 해당 방향을 한 번 씩 더해나가면서 체크를 해준다. 하지만 Queue를 사용하고 있지 않은 지금은 얼만큼이나 반복문을 주어야하는지 모르므로 while(true)를 통해 일단 반복문이 돌면서 해당 방향으로 계속 좌표를 변경해 나가고 벽이나 맵을 나가면 break 문으로 나오도록 하였다.

▶ 바로위의 각 CCTV 별로 여러 방향 탐색을 위해서 이 while문을 for문으로 감싸 index를 더해 주었다. 2번의 경우는 for문의 변수 증가를 +2로 해주어 양 쪽 방향을 탐색해주도록 하였다.

다다다다음 생각

이전 [백준] 14502번 연구소 문제나 [백준] 12100번 2048 (Easy) 나 [모의 SW 역량테스트] 벽돌 깨기 문제와 같이 새로운 조건으로 탐색을 시작하면, 원 배열을 보존해야지 다른 조합으로의 탐색도 진행할 수 있으므로 새로운 조건마다 copy[][]을 원 배열로 초기화 시켜주었다.

방안

1) 방향을 가장한 모든 조합을 만들어보는 문제였다. 90도를 어떻게 돌리냐에 따라 많은시간이 걸릴 수도 있고 적은 시간이 걸릴 수도 있는 문제 같다.

package baekjoon.swtest;
 
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Q15683 {
    static int n,m;
    static int[][] arr;
    static List<Pair> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // 세로 크기
        m = sc.nextInt(); // 가로 크기
        arr = new int[n][m];
        copy = new int[n][m];
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                arr[i][j] = sc.nextInt();
                if(arr[i][j]>0&&arr[i][j]<6)
                    list.add(new Pair(i,j,arr[i][j],0));
            }
        }
        // cctv를 돌리면서 모든 경우를 살펴보자
        result = 100;
        solve(0);
        System.out.println(result);
    }
    
    
    static int[][] copy;
    private static void init() {
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++)
                copy[i][j] = arr[i][j];
        }
    }
    
    // 우 하 좌 상
    static int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};
    private static void check(Pair t) {
        int tx = t.x,ty = t.y;
        switch (t.n) {
        case 1: // 한쪽
            while(true) {
                tx = tx+dir[t.r][0];
                ty = ty+dir[t.r][1];
                if(tx<0 || ty<0 || tx>=n || ty>=m) break;
                // 감시구역 바꿔주기
                if(copy[tx][ty]==0) copy[tx][ty]=-1;
                // 벽 만날경우 종료
                else if(copy[tx][ty]==6) break;
            }
            break;
        case 2: // 양쪽
            for(int i=0;i<3;i+=2) {
                tx = t.x; ty = t.y;
                while(true) {
                    tx = tx+dir[(t.r+i)%4][0];
                    ty = ty+dir[(t.r+i)%4][1];
                    if(tx<0 || ty<0 || tx>=n || ty>=m) break;
                    // 감시구역 바꿔주기
                    if(copy[tx][ty]==0) copy[tx][ty]=-1;
                    // 벽 만날경우 종료
                    else if(copy[tx][ty]==6) break;
                }
            }
            break;
        case 3: // ㄴ
            for(int i=0;i<2;i++) {
                tx = t.x; ty = t.y;
                while(true) {
                    tx = tx+dir[(t.r+i)%4][0];
                    ty = ty+dir[(t.r+i)%4][1];
                    if(tx<0 || ty<0 || tx>=n || ty>=m) break;
                    // 감시구역 바꿔주기
                    if(copy[tx][ty]==0) copy[tx][ty]=-1;
                    // 벽 만날경우 종료
                    else if(copy[tx][ty]==6) break;
                }
            }
            break;
        case 4: // ㅗ
            for(int i=0;i<3;i++) {
                tx = t.x; ty = t.y;
                while(true) {
                    tx = tx+dir[(t.r+i)%4][0];
                    ty = ty+dir[(t.r+i)%4][1];
                    if(tx<0 || ty<0 || tx>=n || ty>=m) break;
                    // 감시구역 바꿔주기
                    if(copy[tx][ty]==0) copy[tx][ty]=-1;
                    // 벽 만날경우 종료
                    else if(copy[tx][ty]==6) break;
                }
            }
            break;
        case 5: // +
            for(int i=0;i<4;i++) {
                tx = t.x; ty = t.y;
                while(true) {
                    tx = tx+dir[(t.r+i)%4][0];
                    ty = ty+dir[(t.r+i)%4][1];
                    if(tx<0 || ty<0 || tx>=n || ty>=m) break;
                    // 감시구역 바꿔주기
                    if(copy[tx][ty]==0) copy[tx][ty]=-1;
                    // 벽 만날경우 종료
                    else if(copy[tx][ty]==6) break;
                }
            }
            break;
        }
    }
    
    static int result;
    private static void solve(int idx) {
        // idx가 끝에 도달하면 정해진 값들로 범위 파악
        if(idx>=list.size()) {
            // copy 배열 초기화
            init();
            for(Pair t: list)
                check(t);
            int cnt = 0;
            for(int i=0;i<n;i++) {
                for(int j=0;j<m;j++) 
                    if(copy[i][j]==0) cnt++;
            }
            result = Math.min(result, cnt);
            return;
        }
        
 
        // 방향을 0 1 2 3으로 조정
        for(int i=0;i<=3;i++) {
            list.get(idx).r=i;
            solve(idx+1);
        }
    }
    
    static class Pair{
        private int x,y,n,r;
        Pair(int x,int y,int n,int r){
            this.x = x;
            this.y = y;
            this.n = n;
            this.r = r;
        }
    }
}