[백준] 15683 감시

문제보기

삼성 역태 준비중!

4번 카메라에서 똑같은거 두번 썼다가 이유를 알 수 없는 틀렸습니다 수렁에 빠졌다.. ㅠㅠ

백준의 테스트케이스는 진짜 촘촘하다!!

import java.util.*;
import java.io.*;
public class Main{
  static int[][] cam; // 카메라 종류, x좌표, y좌표를 담을 배열
  static int cidx; // 카메라 갯수
  static int min; // 최소 사각지대 갯수
  static int[][] map; // 주어진 맵
  static int n; // 주어진 n
  static int m; // 주어진 m

  // 카메라가 왼쪽을 바라볼때 
  static int[][] left(int[][] b, int x, int y){
    // 새로운 배열에 담습니다 
    int[][] c = new int[n][m];
    for(int i = 0 ; i < n ; i++){
      System.arraycopy(b[i], 0 , c[i], 0, m);
    }
    // 카메라 위치의 왼쪽부터 서서히 채워갑니다 
    for(int j = y-1 ; j >= 0 ; j--){
      if(map[x][j] == 6) break; // 벽을 만나면 빠져나옵니다 
      else if(map[x][j] != 0) continue; // 카메라를 만나면 통과 
      c[x][j] = 7; // 카메라 감시구역으로 표시하기
    }
    return c; // 감시구역이 표시된 배열을 반환합니다 
  }

  // 카메라가 오른쪽을 바라 볼때 - 위 함수와 같은 원리 
  static int[][] right(int[][] b, int x, int y){
    int[][] c = new int[n][m];
    for(int i = 0 ; i < n ; i++){
      System.arraycopy(b[i], 0 , c[i], 0, m);
    }
    for(int j = y+1 ; j < m ; j++){
      if(map[x][j] == 6) break;
      else if( map[x][j] != 0) continue;
      c[x][j] = 7;
    }
    return c;       
  }
  // 카메라가 위를 바라 볼때 - 위 함수와 같은 원리 
  static int[][] up(int[][] b, int x, int y){
    int[][] c = new int[n][m];
    for(int i = 0 ; i < n ; i++){
      System.arraycopy(b[i], 0 , c[i], 0, m);
    }
    for(int i = x-1 ; i >= 0 ; i-- ){
      if(map[i][y] == 6) break;
      else if(map[i][y] != 0) continue;
      c[i][y] = 7;
    }
    return c;       
  }
  // 카메라가 아래를 바라 볼때 - 위 함수와 같은 원리 
  static int[][] down(int[][] b, int x, int y){
    int[][] c = new int[n][m];
    for(int i = 0 ; i < n ; i++){
      System.arraycopy(b[i], 0 , c[i], 0, m);
    }
    for(int i = x+1 ; i < n ; i++ ){
      if(map[i][y] == 6 ) break;
      else if(map[i][y] != 0) continue;
      c[i][y] = 7;
    }
    return c;       
  }

  // 재귀 함수 
  static void go(int idx, int[][] a){

    if(idx == cidx){ // 모든 카메라를 다 사용했다면 종료하기
      int cnt = 0; // 사각지대를 담을 변수 
      for(int i = 0 ; i < n ; i++ ){
        for(int j = 0 ; j < m ; j++){
          if(a[i][j] == 0){ // 사각지대 일 때
            cnt++;
          }
        }
      }
      // 전역으로 선언된 사각지대 최소갯수를 갱신합니다
      if( min > cnt){
        min = cnt;
      }
      return;
    }


    int cctv = cam[idx][0]; // cctv의 종류 
    int x = cam[idx][1]; // 그 cctv의 행 위치
    int y = cam[idx][2]; // 그 cctv의 열 위치 

    // 인자로 받은 배열을 새로운 배열로 옮겨 담습니다 
    int[][] b = new int[n][m];
    for(int i = 0 ; i < n ; i++){
      System.arraycopy(a[i], 0 , b[i], 0, m);
    }

    if(cctv == 1){ // 1번카메라는 동서남북 중 한 방향만 감시 
      go(idx+1, left(b, x, y));
      go(idx+1, right(b, x, y));
      go(idx+1, up(b, x, y));
      go(idx+1, down(b, x, y));
    }else if(cctv == 2){ // 2번 카메라는 수평, 수직 중 감시(룩?)
      // horizen
      go(idx+1, left(right(b, x, y), x, y));
      // vertical
      go(idx+1, up(down(b, x, y), x, y));

    }else if(cctv == 3){ // 3번 카메라는 90도 방향으로 감시 
      // up right
      go(idx+1, up(right(b,x,y),x,y));
      // right down
      go(idx+1, right(down(b,x,y),x,y));
      // down left
      go(idx+1, left(down(b,x,y),x,y));
      // left up
      go(idx+1, left(up(b,x,y),x,y));
    }else if(cctv == 4){ // 4번 카메라는 ㅗ 모양으로 감시 
      // no left
      go(idx+1, right(up(down(b,x,y),x,y),x,y));
      // no right
      go(idx+1, left(up(down(b,x,y),x,y),x,y));
      //no up
      go(idx+1, right(left(down(b,x,y),x,y),x,y));
      //no down
      go(idx+1, right(up(left(b,x,y),x,y),x,y)); 

    }else{ // 5번 카메라는 동서남북 모두 감시 
      // all direction
      go(idx+1, left(right(up(down(b,x,y),x,y),x,y),x,y));
    }

  }
  public static void main(String []args) throws 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());
    map = new int[n][m];
    cam = new int[8][3];
    cidx = 0;
    for(int i = 0 ; i < n ; i++ ){
      st = new StringTokenizer(br.readLine());
      for(int j = 0 ; j < m ; j++){
        map[i][j] =  Integer.parseInt(st.nextToken());
        if(!(map[i][j] == 0 || map[i][j] == 6)){
          cam[cidx][0] = map[i][j];
          cam[cidx][1] = i;
          cam[cidx][2] = j;
          cidx++;
        }
      }
    }
    min = 2000000000;
    go(0, map);
    System.out.println(min);
  }
}