[SWEA] 5656 벽돌깨기

문제보기

라인 코테 통과했다~~ 토요일에 필기 시험 보러간다 ㅠㅠ

늦은감이 매우 크지만 오늘부터 정처기라도 봐야겠다(…)

오늘의 문풀은 딱 여기까지만! 집에가서 책 읽어봐야지 @_@

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
// 좌표를 저장할 클래스 - BFS에서 사용
class Pair{
  int x;
  int y;
  Pair(int x, int y){
    this.x = x;
    this.y = y;
  }
}

public class Main {

  static int n;
  static int w;
  static int h;
  static int remain;
  static int[] dx = {1, -1, 0, 0};
  static int[] dy = {0, 0, 1, -1};

  static int bfs(int[][] map, int i, int j) {
    Queue<Pair> q = new LinkedList<Pair>();
    q.add(new Pair(i, j));

    while(!q.isEmpty()) {
      Pair p = q.remove();
      int x = p.x;
      int y = p.y;
      int num = map[x][y]; // 미리 값을 빼주고
      map[x][y] = 0; // 0으로 처리해줘야 중복으로 안부순다
			
      // 벽돌에 적힌 숫자만큼 상하좌우 다 뿌순다
      for(int l = 1 ; l < num ; l++ ) {
        for(int k = 0 ; k < 4 ; k++) {
          int nx = x + dx[k]*l;
          int ny = y + dy[k]*l;

          if(nx>=0 && nx < h && ny >= 0 && ny< w) {
            if(map[nx][ny] != 0) {
              q.add(new Pair(nx,ny));

            }
          }
        }
      }		
    }
    // 건재한 블럭의 갯수 세기
    int bricks = 0;
    for(int ii = 0 ; ii < h ; ii++) {
      for(int jj = 0 ; jj < w ; jj++) {
        if(map[ii][jj] != 0) {
          bricks++;
        }
      }
    }
    return bricks; // 반환해준다
  }


  static void go(int[][] map, int cnt, int brick) {
    // 종료 조건 1 - 모든 횟수를 소진 했을 때 
    if(cnt >= n) {
      if(remain > brick) {
        remain = brick; // 최소 남은 블럭 갯수 갱신
      }
      return;
    }
		// 종료 조건 2 - 더이상 깰 블럭이 없을때를 위한 변수
    boolean allBroken = true; 
    
    for(int j = 0 ; j < w ; j++) {
      for(int i = 0 ; i < h ; i++) {
        if(map[i][j] != 0) {
          allBroken = false; // 아직 깰게 남았다

          int num = map[i][j]; // 적힌 숫자가
          
          if(num == 1) { // 1일때는 걔만 뿌시면 된다 
            map[i][j] = 0;
            go(map, cnt+1, brick-1);
            map[i][j] = num; // 원상복구 해주자 
            
          }else { // 적힌 숫자가 1보다 크다면 
            int[][] map2 = new int[h][w]; // 원상복구할 엄두가 안나므로 미리 복사해서 쓰자
            for(int row = 0 ; row < h ; row++) {
              System.arraycopy(map[row], 0, map2[row], 0, w);
            }
						
            // bfs를 통해 뿌셔뿌셔 해주자
            int bricks = bfs(map2, i, j);

            // arrange map - 곳곳에 빈 0이 있다면 중력 처리 해주자
            for(int col = 0 ; col < w ; col++) {
              // 이럴땐 스택쓰면 참 편하더라~~ 자료구조 배우길 잘했다
              Stack<Integer> stack = new Stack<Integer>();
              for(int row = 0 ; row < h ; row++) {
                if(map2[row][col] != 0) {
                  stack.push(map2[row][col]);
                  map2[row][col] = 0;
                }
              }
              int hh = h;
              while(!stack.isEmpty()) {
                map2[hh-- -1][col] = stack.pop();
              }
            }
						// 재귀호출
            go(map2, cnt+1, bricks);
          }
          break; // 각 컬럼의 맨 상단만 구슬이 닿을 수 있으므로 빠져나옴
        }
      }
    }
    // 종료 조건 2 - 더이상 깰 블럭이 없을 때
    if(allBroken) {
      if(remain > brick) {
        remain = brick;
      }

      return;
    }
  }


  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int t = Integer.parseInt(br.readLine());

    int idx = 1;
    StringBuilder sb = new StringBuilder();
    while(t-->0) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      n = Integer.parseInt(st.nextToken());
      w = Integer.parseInt(st.nextToken());
      h = Integer.parseInt(st.nextToken());
      int[][] map = new int[h][w];

      remain = 0;
      for(int i = 0 ; i < h ; i++) {
        st = new StringTokenizer(br.readLine());
        for(int j = 0 ; j < w ; j++) {
          map[i][j] = Integer.parseInt(st.nextToken());
          if(map[i][j] != 0) {
            remain++; // 부술 수 있는 벽돌의 갯수를 센다
          }
        }
      }

      go(map, 0, remain);
      sb.append("#" + idx++ + " " + remain + "\n");
    }

    System.out.println(sb);
  }
}