백준 15683 감시 Java

삼성 SW 역량테스트 기출문제이다.

 

CCTV의 종류는 5가지이고 회전이 가능하다.

따라서 0 -> 동, 1 -> 서, 2 -> 남, 3 -> 북 이라고 할 때

1번은 1, 2, 3, 4 = 4가지

2번은 01, 23 = 2가지 

3번은 02, 03, 12, 13 = 4가지

4번은 012, 013, 023, 123 = 4가지

5번은 0123 = 1가지이다.

 

DFS로 1~5까지 수를 만났을 때 

수에 맞는 각각의 경우를 감시할 수 있는 범위를 배열에 표시해준 다음에

DFS를 다음 수로 재귀 호출하고

돌아와서 표시해준 수를 다시 0으로 만들어 주는 백트래킹 방식으로 해결하였다.

 

이렇게 하면 DFS를 타고 타고 모든 경우의 CCTV 범위의 사각지대의 수를 찾을 수 있다.

 

monitor라는 메소드를 만들어서 현재 위치, 방향, 찾을 수, 바꿀 수를 입력하면

CCTV가 감시할 수 있는 범위의 배열의 값을 초기화해주는 방식으로 표시해주었다.

 

처음엔 CCTV의 범위를 표시하는 수를 간단하게 설정해서

여러 대의 CCTV의 범위가 겹칠 때

지워지지 말아야 하는 수가 지워지면서 틀렸었다.

 

그래서 DFS에 매개 변수로 cnt변수를 추가하여 몇 번째 재귀 호출인지 

표시하여 배열에 cnt번째 재귀 호출에 CCTV범위를 cnt로 초기화하는 방식으로

그 당시 호출에서 초기화한 범위만 cnt를 통해 찾아서 지우니 해결할 수 있었다.

 

cnt는 다른 수들과 겹치지 않기 위해 음수로 했다.

import java.io.*;
import java.util.*;
 
public class Q15683 {
    static int n,m;
    static int[][] map;
    static int[] tx = {0, 0, 1, -1};
    static int[] ty = {1, -1, 0, 0};
    static int min = Integer.MAX_VALUE;
 
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(reader.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
 
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(reader.readLine());
            for(int j=0; j<m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        dfs(0, -1);
        System.out.println(min);
    }
 
    static void dfs(int idx, int cnt) {
        if(idx == n * m) { //배열의 끝까지 도착
            min = Math.min(min, count());
            return;
        }
        
        int r = idx / m;
        int c = idx % m;
        
        if(map[r][c] == 1) { //0, 1, 2, 3
            for(int i=0; i<4; i++) {
                monitor(idx, i, 0, cnt);
                dfs(idx+1, cnt-1);
                monitor(idx, i, cnt, 0);
            }
        } else if(map[r][c] == 2) { //01, 23
            for(int i=0; i<4; i+=2) {
                monitor(idx, i, 0, cnt);
                monitor(idx, i+1, 0, cnt);
                dfs(idx+1, cnt-1);
                monitor(idx, i, cnt, 0);
                monitor(idx, i+1, cnt, 0);
            }
        } else if(map[r][c] == 3) { //02, 03, 12, 13
            for(int i=0; i<2; i++) {
                monitor(idx, i, 0, cnt);
                for(int j=2; j<4; j++) {
                    monitor(idx, j, 0, cnt);
                    dfs(idx+1, cnt-1);
                    monitor(idx, j, cnt, 0);
                }
                monitor(idx, i, cnt, 0);
            }
        } else if(map[r][c] == 4) { //012, 013, 023, 123
            for(int i=3; i>=0; i--) {
                for(int j=0; j<4; j++) {
                    if(i==j) continue;
                    monitor(idx, j, 0, cnt);
                }
                dfs(idx+1, cnt-1);
                for(int j=0; j<4; j++) {
                    if(i==j) continue;
                    monitor(idx, j, cnt, 0);
                }
            }
        } else if(map[r][c] == 5) { //0123
            for(int i=0; i<4; i++) {
                monitor(idx, i, 0, cnt);
            }
            dfs(idx+1, cnt-1);
            for(int i=0; i<4; i++) {
                monitor(idx, i, cnt, 0);
            }
        } else dfs(idx+1, cnt-1); //1~5까지 수가 아닐 때 다음 수로 호출
    }
    
    static void monitor(int idx, int dir, int orignal, int change) { //한가지 방향만 채워줌
        int r = idx / m;
        int c = idx % m;
        while(true) {
            r += tx[dir];
            c += ty[dir];
            if(r>=0 && r<n && c>=0 && c<m) {
                if(map[r][c] == 6) break;
                if(map[r][c] == orignal) map[r][c] = change;
            } else {
                break;
            }
        }
    }
    
    static int count() {
        int cnt = 0;
        for(int[] temp : map) {
            for(int v : temp) {
                if(v==0) cnt++;
            }
        }
        return cnt;
    }
}