SWEA[5656] - 벽돌 깨기

링크

SWEA[5656]

문제설명

• 완전탐색 + 시뮬레이션

문제풀이

• 완전탐색 + 시뮬레이션

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution5656 {

    public static int[][] dir = {
            {-1,0},    
            {1,0},    
            {0,-1},    
            {0,1}    
    };

    public static int Ans = Integer.MAX_VALUE;
    public static int[][] map;
    public static int[][] n_map;
    public static int N;
    public static int W;
    public static int H;
    public static int[] shoot_serial;

    public static void Down() {
        int temp;

        for (int i = 0; i < W; i++) {
            for (int s = 0; s < H-1; s++) {
//                밑에서부터 계산하면서 내림
                for (int h = H-2; h >= 0; h--) {
                    if(n_map[h][i]>0 && n_map[h+1][i]==0) {
                        temp = n_map[h][i];
                        n_map[h][i] = n_map[h+1][i];
                        n_map[h+1][i] = temp;
                    }
                }
            }
        }
    }

    public static void Pop(int[] rc) {
        int range = n_map[rc[0]][rc[1]];

        int nr;
        int nc;
        if(range>0) {
            n_map[rc[0]][rc[1]]=0;
            for (int d = 0; d < 4; d++) {
                for (int i = 1; i < range; i++) {
                    nr = rc[0]+i*dir[d][0];
                    nc = rc[1]+i*dir[d][1];
//                    경계 안에서
                    if(nr>=0 && nr<H && nc>=0 && nc<W) {
                        if(n_map[nr][nc]>0) {
                            Pop(new int[] {nr,nc});
                        }
                    }
                }
            }
        }
    }

    public static void Shoot(int w) {
        for (int i = 0; i < H; i++) {
            if(n_map[i][w]>0) {
                Pop(new int[] {i,w});
                return;
            }
        }
    }

    public static void Search(int cnt) {
//        공 N번 다던짐
        if(cnt==N) {
//            System.out.println(Arrays.toString(shoot_serial));
//            n_map 초기화
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    n_map[i][j] = map[i][j];
                }
            }
//            shoot_serial 기준으로 simulation 실행
//            shoot_serial = new int[]{2,2,6};
            for (int i = 0; i < N; i++) {
                Shoot(shoot_serial[i]);
                Down();
            }
//            벽돌 갯수 세서 Ans 갱신
            int temp=0;
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    if(n_map[i][j]>0)temp++;
                }
            }
            Ans = Math.min(Ans, temp);
            return;
        }
        for (int i = 0; i < W; i++) {
            shoot_serial[cnt]=i;
            Search(cnt+1);
        }
    }

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/swea/5656.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T=Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= T; test_case++) {
//            입력
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            H = Integer.parseInt(st.nextToken());
            map = new int[H][W];
            n_map = new int[H][W];
            shoot_serial = new int[N];

            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());
                }
            }

            Search(0);

            System.out.println("#"+test_case+" "+Ans);
            /*
             * 초기화
             */
            Ans=Integer.MAX_VALUE;
        }//end test_case
    }//end main
}

아쉬운점

• 배열 인덱스 헷갈림
  • 제일 위에가 [r]==[0]임

잘한점

• O(N) = W^N*Simulation = 12^4*Simulation = 20000*Simulation 안터짐
  • 완전탐색
• n_map 모든 공 던지는 순서마다 초기화
• Pop() 연쇄작용 재귀로 구현
  • 연쇄작용의 말단부터 터트리면서 그전에 이미 터진애들 체크하므로 문제안됨
• Down() 함수는 밑에서부터 위로 올라가면서 체크해야 안걸림