[BOJ] 15683. 감시

이문제는 복잡한 구현 문제이다.

문제에 주어진 대로 구현을 하면 되는데, 구현을 함에 있어 재귀와 다양한 함수를 활용하였다. 재귀와 백트래킹을 같이 사용하였는데 2차원 배열의 백트래킹을 할땐 재귀함수 안에서 지역변수로 temp[][] 를 선언하고 원래 2차원 배열을 복사해놓고 재귀가 끝나면 다시 붙여넣는 작업을 통해 백트래킹을 구현할 수 있다. 이 부분에 있어 전역변수로 하다가 코드가 꼬이는 현상이 발생했는데 필히 지역변수를 사용해야 한다.

package boj2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main_bj_15683_감시 {
    static int[][] map;
    
    static int[] di= {-1,0,1,0};
    static int[] dj= {0,1,0,-1};
    
    static List<Pos> cctvs;
    
    static int R,C;
    
    static int answer;
    
    static class Pos{
        int i,j,sort;
        Pos (int i,int j,int s){
            this.i=i;this.j=j;sort=s;
        }
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        st=new StringTokenizer(br.readLine());
        R=Integer.parseInt(st.nextToken());
        C=Integer.parseInt(st.nextToken());
        
        cctvs=new ArrayList<>();
        map=new int[R][C];
        
        for(int i=0;i<R;i++) {
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<C;j++) {
                map[i][j]=Integer.parseInt(st.nextToken());
                if(map[i][j]!=0 && map[i][j]!=6)
                    cctvs.add(new Pos(i, j, map[i][j]));
            }
        }
        
        answer=Integer.MAX_VALUE;
        dfs(0);
        System.out.println(answer);
    }
    
    static void dfs(int index) {
        if(index==cctvs.size()) {
            int count=0;
            for(int i=0;i<R;i++) {
                for(int j=0;j<C;j++) {
                    if(map[i][j]==0)
                        count+=1;
                }
            }
            answer=Math.min(answer, count);
            return;
        }
        
        Pos cctv=cctvs.get(index);
        
        int[][] tempArray=new int[R][C];
        
        if(cctv.sort==1) {
            for(int dir=0;dir<4;dir++) {
                backup(tempArray);
                move(cctv,dir);
                dfs(index+1);
                recover(tempArray);
            }
        }else if(cctv.sort==2) {
            for(int dir=0;dir<2;dir++) {
                backup(tempArray);
                move(cctv,dir);
                dfs(index+1);
                recover(tempArray);
            }
        }else if(cctv.sort==3) {
            for(int dir=0;dir<4;dir++) {
                backup(tempArray);
                move(cctv,dir);
                dfs(index+1);
                recover(tempArray);
            }
        }else if(cctv.sort==4) {
            for(int dir=0;dir<4;dir++) {
                backup(tempArray);
                move(cctv,dir);
                dfs(index+1);
                recover(tempArray);
            }
        }else if(cctv.sort==5) {
            backup(tempArray);
            move(cctv,0);
            dfs(index+1);
            recover(tempArray);
        }
    }
    
    static void backup(int[][] tempArray) {
        for(int i=0;i<R;i++) {
            for(int j=0;j<C;j++) 
                tempArray[i][j]=map[i][j];
        }
    }
    static void recover(int[][] tempArray) {
        for(int i=0;i<R;i++) {
            for(int j=0;j<C;j++) 
                map[i][j]=tempArray[i][j];
        }
    }
    
    
    static void move(Pos cctv,int dir) {
        if(cctv.sort==1) {
            change(cctv.i,cctv.j,dir);
        }else if(cctv.sort==2){
            if(dir==0) {
                change(cctv.i,cctv.j,0);change(cctv.i,cctv.j,2);
            }else if(dir==1) {
                change(cctv.i,cctv.j,1);change(cctv.i,cctv.j,3);
            }
        }else if(cctv.sort==3) {
            if(dir==0) {
                change(cctv.i,cctv.j,0);change(cctv.i,cctv.j,1);
            }else if(dir==1) {
                change(cctv.i,cctv.j,1);change(cctv.i,cctv.j,2);
            }else if(dir==2) {
                change(cctv.i,cctv.j,2);change(cctv.i,cctv.j,3);
            }else if(dir==3) {
                change(cctv.i,cctv.j,3);change(cctv.i,cctv.j,0);
            }
        }else if(cctv.sort==4) {
            for(int index=0;index<4;index++) {
                if(dir!=index) {
                    change(cctv.i,cctv.j,index);
                }
            }
        }else if(cctv.sort==5) {
            for(int index=0;index<4;index++) {
                change(cctv.i,cctv.j,index);
            }
        }
    }
 
    static void change(int i,int j,int dir) {
        while(true) {
            i=i+di[dir];
            j=j+dj[dir];
            
            if(i<0 || i>=R || j<0 ||j>=C)    //범위밖
                break;
            
            if(map[i][j]==6)    //cctv또는 벽
                break;
            
            if(1<=map[i][j] && map[i][j]<=5)
                continue;
            
            if(map[i][j]==0 || map[i][j]==-1)
                map[i][j]=-1;
        }
    }
}