벽돌깨기

문제 :https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo&categoryId=AWXRQm6qfL0DFAUo&categoryType=CODE

SW Expert Academy

알고리즘

1. 완전 탐색 하였고 1이 아닌 벽돌은 -1을 더해줬고, 1에서 구슬을 만나면 터지기 때문에 터질 경우 check함수를 통해 터진 벽돌을 -1로 표시한다.

2. -1로 표시된 벽돌을 0으로 바꿔주기 위해 큐를 이용했다. 아래 오른쪽부터 스캔하여 -1인 벽돌은 큐에 넣어주고 다시 스캔한다.

3. 스캔하다가 -1도 아니고 0도 아닌 벽돌은 떨어뜨려줘야 하기 때문에 큐에서 뺸 좌표 값에(-1인 벽돌 자리) 넣어주고 자기 자리를 0으로 만든다.

4. 1~3 진행 후 남은 벽돌은 count하고 min아랑 비교 한다.

주의사항

1. 구슬을 던질 수 있는 최대 횟수가 4번이고 던질 수 있는 곳이 12개기 때문에 12개중 4개를 순서있이 중복없이 뽑는 것과 같다. 즉 12의 4승 약 20000번이다. 그러나 1번 당 반복문이 많이 돌기 때문에 시간초과를 생각하며 구현해야한다.

2. 문제 조건을 꼼꼼히 읽어본다.

구현

class Solution_벽돌깨기
{
    static int map[][];
    static int temp[][];
    static int index[];
    static int min;
    static int K,M,N;
    static int dir[][] = {{-1,0},{1,0},{0,-1},{0,1}};
    static LinkedList<int []> queue = new LinkedList<int[]>();

    public static void main(String args[]) throws Exception
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine());
        for(int test_case = 1; test_case <= T; test_case++)
        {
            StringTokenizer s = new StringTokenizer(in.readLine()," ");
            K = Integer.parseInt(s.nextToken());
            M = Integer.parseInt(s.nextToken()); // 가로
            N = Integer.parseInt(s.nextToken()); // 세로
            map = new int[N][M];
            temp = new int[N][M];
            index = new int[K];
            for (int i = 0; i < N; i++) {
                s = new StringTokenizer(in.readLine()," ");
                for (int j = 0; j < M; j++) {
                    map[i][j] = Integer.parseInt(s.nextToken());
                    temp[i][j] = map[i][j];
                }
            }
            min =Integer.MAX_VALUE;
            DFS(0);
            System.out.println("#"+test_case+" "+min);
        }
    }
    private static void DFS(int i) {
        if(i == K)
        {
            /////////////////////////////////복사///////////////////
            for (int j = 0; j < N; j++) {
                for (int j2 = 0; j2 < M; j2++) {
                    map[j][j2] = temp[j][j2]; 
                }
            }
            //////////////////////체크함수///////////////////
            for (int z = 0; z < K; z++) 
            {
                for (int j = 0; j < N; j++) {
                    if(map[j][index[z]] != 0)
                    {
                        check(j,index[z]);
                        break;
                    }
                }
                //update 아래에서 위로 스캔했다.
                for (int j = M-1; j > -1; j--) {
                    for (int j2 = N-1; j2 > -1; j2--) {
                        if(map[j2][j] == -1) {
                            queue.offer(new int[] {j2,j}); //-1인 벽돌 위치 큐에 넣는다.
                            map[j2][j] = 0; // 빈자리로 만듬
                        }
                        else if(map[j2][j] !=0 && !queue.isEmpty()) //-1아니고 0도 아니고 큐도 안비었으면
                        {
                            int temp[] = queue.poll();  
                            map[temp[0]][temp[1]] = map[j2][j]; //-1벽돌위치에 넣어준다 -> 떨어뜨려줌
                            map[j2][j] = 0; // 빈자리로 만듬 
                            queue.offer(new int[] {j2,j});
                        }
                    }
                    queue.clear();
                }    
            }

            int cnt=0;
            // 남아있는 벽돌 수 카운트
            for (int j = 0; j < N; j++) {
                for (int j2 = 0; j2 < M; j2++) {
                    if(map[j][j2]!=0)
                        cnt++;
                }
            }
            if(min > cnt)
                min = cnt;
            return;
        }
        for (int j = 0; j < M; j++) { //완전탐색 최대 4번이기 때문에 시간초과 안난다고 생각
            index[i] = j;
            DFS(i+1);
        }
    }
    private static void check(int j, int temp1) {
        int end = map[j][temp1];
        map[j][temp1] = -1;
        for (int j2 = 1; j2 <end; j2++) {
            for (int k = 0; k < 4; k++) {
                int ny = j + dir[k][0] *j2;
                int nx = temp1+dir[k][1] * j2;
                if(ny > -1 && nx > -1 && ny < N && nx < M)
                {
                     if(map[ny][nx]>1 && map[ny][nx] < 10) 
                         check(ny,nx);
                     else if(map[ny][nx] !=0)
                         map[ny][nx] = -1;
                }
            }
        }
    }
}