백준 15683번 감시

문제 링크 : https://www.acmicpc.net/problem/15683

문제 접근

1. 완전탐색으로 cctv의 방향이 바뀌는 모든 경우를 체크하여 사각지대가 가장 적은 경우의 사각지대 수를 출력하였다.

2. 솔직히 완전탐색은 풀이를 어케 써야될지 모르겠다. 그냥 가능한 경우를 모두 봐주면 된다.

소스 코드

import java.util.ArrayList;
import java.util.Scanner;
 
public class Main {
    
    static int[][] map;
    static int n, m, mincnt;
    static ArrayList<Cctv> ar = new ArrayList<Cctv>();
    static int[] dy = { -1, 0, 1, 0 };
    static int[] dx = { 0, 1, 0, -1 };
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt();
        m = sc.nextInt();
        
        map = new int[n][m];
        
        mincnt = n*m;
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                int t = sc.nextInt();
                map[i][j] = t;
                if(t>=1 && t<=5) {
                    ar.add(new Cctv(i, j, t));
                }
            }
        }
        
        recur(0);
        
        System.out.println(mincnt);
    }
    
    static void recur(int index) {
        if(index==ar.size()) {
            int cnt=0;
            
            for(int i=0; i<n; i++) {
                for(int j=0; j<m; j++) {
                    if(map[i][j]==0) cnt++;
                }
            }
            
            if(mincnt > cnt)
                mincnt = cnt;
            
            return;
        }
        
        Cctv tmp = ar.get(index);
        
        switch (tmp.cctvType) {
        case 1 :
            
            for(int i=0; i<4; i++) {
                int[][] tmpmap = new int[n][m];
                for(int j=0; j<n; j++) {
                    for(int k=0; k<m; k++) {
                        tmpmap[j][k] = map[j][k];
                    }
                }
                
                fillcctv(tmp.y, tmp.x, i);
                
                recur(index+1);
                
                for(int j=0; j<n; j++) {
                    for(int k=0; k<m; k++) {
                        map[j][k] = tmpmap[j][k];
                    }
                }
            }
            
            break;
            
        case 2 :
            
            for(int i=0; i<2; i++) {
                int[][] tmpmap = new int[n][m];
                for(int j=0; j<n; j++) {
                    for(int k=0; k<m; k++) {
                        tmpmap[j][k] = map[j][k];
                    }
                }
                
                fillcctv(tmp.y, tmp.x, i);
                fillcctv(tmp.y, tmp.x, i+2);
                
                recur(index+1);
                
                for(int j=0; j<n; j++) {
                    for(int k=0; k<m; k++) {
                        map[j][k] = tmpmap[j][k];
                    }
                }
            }
            
            break;
            
        case 3 :
            
            for(int i=0; i<4; i++) {
                int[][] tmpmap = new int[n][m];
                for(int j=0; j<n; j++) {
                    for(int k=0; k<m; k++) {
                        tmpmap[j][k] = map[j][k];
                    }
                }
                
                fillcctv(tmp.y, tmp.x, i);
                if(i==3)
                    fillcctv(tmp.y, tmp.x, 0);
                else
                    fillcctv(tmp.y, tmp.x, i+1);
                
                recur(index+1);
                
                for(int j=0; j<n; j++) {
                    for(int k=0; k<m; k++) {
                        map[j][k] = tmpmap[j][k];
                    }
                }
            }
                
            break;
            
        case 4 : 
            
            for(int i=0; i<4; i++) {
                
                int[][] tmpmap = new int[n][m];
                for(int j=0; j<n; j++) {
                    for(int k=0; k<m; k++) {
                        tmpmap[j][k] = map[j][k];
                    }
                }
                
                for(int j=0; j<4; j++) {
                    if(i==j) continue;
                    fillcctv(tmp.y, tmp.x, j);
                }
                
                recur(index+1);
                
                for(int j=0; j<n; j++) {
                    for(int k=0; k<m; k++) {
                        map[j][k] = tmpmap[j][k];
                    }
                }
            }
            
            break;
            
        case 5 : 
            
            for(int j=0; j<4; j++) {
                fillcctv(tmp.y, tmp.x, j);
            }
            
            recur(index+1);
            
        }
        
        
        
    }
    
    
    static void fillcctv(int y, int x, int d) {
        switch(d) {
        
        case 0 :
            for(int i = y-1; i>=0; i--) {
                if(map[i][x]==6) break;
                if(map[i][x]>=1 && map[i][x]<=5) continue;
                
                map[i][x] = 9;
            }
            
            break;
            
        case 1 :
            for(int i=x+1; i<m; i++) {
                if(map[y][i]==6) break;
                if(map[y][i]>=1 && map[y][i]<=5) continue;
                
                map[y][i] = 9;
            }
            break;
            
        case 2 :
            for(int i=y+1; i<n; i++) {
                if(map[i][x]==6) break;
                if(map[i][x]>=1 && map[i][x]<=5) continue;
                
                map[i][x] = 9;
            }
            break;
            
        case 3 :
            for(int i=x-1; i>=0; i--) {
                if(map[y][i]==6) break;
                if(map[y][i]>=1 && map[y][i]<=5) continue;
                
                map[y][i] = 9;
            }
            
            break;
        }
    }
    
}
 
 
class Cctv {
    int y;
    int x;
    int cctvType;
    
    Cctv(int y, int x, int cctvType) {
        this.y = y;
        this.x = x;
        this.cctvType = cctvType;
    }
}