<Algorithm> 85. 15683번 감시

1. 15683번 감시

• 삼성 코딩테스트 문제, DFS + 백트레킹을 사용하여 구현했다.

• 어렵다기 보다는 복잡한게 많다. 복붙으로 만들어 중간 중간에 고쳐주질 않으니까 틀리는 부분이 많았다.

• 그리고 실수했는데도 어떻게 또 맞아들어가서 기본 테스트케이스가 통과해버리니까 찾는데 너무 오래 걸렸던거 같다.

• 주의할점은 2차원 배열은 그냥 클론해서 사용하면 주소값을 참조하는 것과 다른 없어지는 부분 조심해야 할 것 같다.

• CCTV의 좌표를 저장하고 dfs로 모든 경우의 수를 체크하여 풀었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
class Pair{
    int x;
    int y;
    int num;
    public Pair(int x, int y, int num) {
        super();
        this.x = x;
        this.y = y;
        this.num = num;
    }
    
}
public class Main {
    public static ArrayList<Pair> cctv = new ArrayList<>();
    public static boolean[][] visited;
    public static int N;
    public static int M;
    
    public static void main(String[] args) throws NumberFormatException, 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());
        int[][] arr = new int[N][M];
        visited = new boolean[N][M];
        
        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());
                if(arr[i][j] >= 1 && arr[i][j] <= 5) {
                   cctv.add(new Pair(i, j, arr[i][j]));
                   visited[i][j] = true;
                }
                if(arr[i][j] == 6) visited[i][j] = true;
            }
        }
        dfs(0, arr.clone());
        
        System.out.println(min);
    }
    public static int min = Integer.MAX_VALUE;
    
    public static void dfs(int idx,int clone[][]) {
        if(idx == cctv.size()) {
            int count = 0;
            
            for(int i = 0 ; i < N; i++) {
                for(int j = 0 ; j < M; j++) {
                    if(visited[i][j] == false) {
                        count++;
                    }
                }
            }
            //System.out.println(count+" "+Arrays.deepToString(visited));
            min = Math.min(min, count);
            return;
            
        } // 갯수 세기
        
        Pair pair = cctv.get(idx);
        
        switch (pair.num) {
        case 1:
        {
            int dir[][] = {{1,0,0,0},{0,1,0,0},{0,0,1,0},{0,0,0,1}};
            boolean[][] temp = new boolean[N][M];
            copy(visited, temp);
            for(int i = 0; i < 4; i++) {
                dirShap(pair, dir[i][0], dir[i][1], dir[i][2], dir[i][3], clone);
                dfs(idx + 1, clone);
                visited = new boolean[N][M];
                copy(temp, visited);
            }
            break;
        }
        case 2:
        {
            int dir[][] = {{1,0,1,0},{0,1,0,1}};
            boolean[][] temp = new boolean[N][M];
            copy(visited, temp);            
            
            for(int i = 0; i < 2; i++) {
                
                //System.out.println(i+"전 2"+Arrays.deepToString(visited));
                dirShap(pair, dir[i][0], dir[i][1], dir[i][2], dir[i][3], clone);
                //System.out.println(i+"후 2"+Arrays.deepToString(visited));
                dfs(idx + 1, clone);
                
                visited = new boolean[N][M];
                copy(temp, visited);
            }
            
            break;
        }
        case 3:
        {
            int dir[][] = {{1,1,0,0},{0,1,1,0},{0,0,1,1},{1,0,0,1}};
            boolean[][] temp = new boolean[N][M];
            copy(visited, temp);            
            
            for(int i = 0; i < 4; i++) {
                dirShap(pair, dir[i][0], dir[i][1], dir[i][2], dir[i][3], clone);
                dfs(idx + 1, clone);
                visited = new boolean[N][M];
                copy(temp, visited);
                
            }
            break;
        }
            
        case 4:
        {
            int dir[][] = {{0,1,1,1},{1,0,1,1},{1,1,0,1},{1,1,1,0}};
            boolean[][] temp = new boolean[N][M];
            copy(visited, temp);        
            
            for(int i = 0; i < 4; i++) {
                dirShap(pair, dir[i][0], dir[i][1], dir[i][2], dir[i][3], clone);
                //System.out.println(i+"전 4"+Arrays.deepToString(visited));
                dfs(idx + 1, clone);
                //System.out.println(i+"후 4"+Arrays.deepToString(visited));
                
                visited = new boolean[N][M];
                copy(temp, visited);
            }
            break;
        }
 
        default:
        {
                boolean[][] temp = new boolean[N][M];
                copy(visited, temp);            
                
                dirShap(pair, 1, 1, 1, 1, clone);
                dfs(idx + 1, clone);
                
                visited = new boolean[N][M];
                copy(temp, visited);
            break;
        }
    }
        
        
        
    }
    
    public static void dirShap(Pair cctv,int u,int l, int d,int r ,int[][] clone) {
        
        if(l == 1) {
            //System.out.println(" "+Arrays.deepToString(visited));
            for(int y = cctv.y; y >= 0; y--) {
                if(clone[cctv.x][y] == 6) {
                    break;
                }
                visited[cctv.x][y] = true;
            }
        }
        
        if(r == 1) {
            for(int y = cctv.y; y < M; y++) {
                if(clone[cctv.x][y] == 6) {
                    break;
                }
                visited[cctv.x][y] = true;
            }
            
        }
        if(u == 1) {
            
            for(int x = cctv.x; x >= 0; x--) {
                if(clone[x][cctv.y] == 6) {
                    break;
                }
                visited[x][cctv.y] = true;
            }
        }
        if(d == 1) {
            for(int x = cctv.x; x < N; x++) {
                if(clone[x][cctv.y] == 6) {
                    break;
                }
                visited[x][cctv.y] = true;
            }
          }
            
    }
    
    public static void copy(boolean [][] orign, boolean[][] copy) {
        for(int i = 0; i < N ; i ++) {
            copy[i] = orign[i].clone();
        }
    }
        
 
}
 

참고 & 출처