[SWEA] 5656번. [모의 SW 역량테스트] 벽돌 깨기 - JAVA

🧷 문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo 

SW Expert Academy

 

📄 풀이 과정

1. 구슬을 떨어트릴 수 있는 위치는 W 개가 있는데(열의 갯수) , 구슬이 N개 있으므로 W^N = 중복 순열로 구현가능하다.

2. c=0 부터 c=W-1 까지 현재 열에 깨질 벽돌이 있는지 찾는다. 

3. 없다면 다음 열로 넘어간다.

4. 깨질 벽돌이 있다면 현재 map 을 newMap에 복사한 후 newMap을 사용하여 벽돌을 깬다. (현재 경우에만 벽돌을 깨고 다음 경우엔 원상복구된 (원래 깨지지 전의 map)을 사용해야 하기 때문이다. 

5. 벽돌은 BFS 를 사용하여 연쇄적으로 깨질 수 있는 모든 벽돌을 깬다. (0으로 저장)

6. down() 에서 공중에 떠있는 벽돌을 아래로 내린다. (전체 열에 대하여, 밑에서부터 빈칸을 찾고, 찾았다면 빈칸 다음 행부터 내릴 벽돌을 찾아 위치를 바꿔준다.)

7. count 를 1 증가시켜 다음 구슬로 넘어간다.

8. 만약 남아있는 벽돌이 없다면 return 하여 남아있던 가지(경우)를 제거한다. (백트랙킹)

9. count가 주어진 구슬의 수가 동일해진다면 남아있던 벽의 갯수를 최솟값으로 갱신한다.

 

💻 코드

import java.io.*;
import java.util.*;
 
public class Solution {
    static int N, W, H, ans;
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    
    static class Point{
        int r, c, scope;
 
        public Point(int r, int c, int scope) {
            super();
            this.r = r;
            this.c = c;
            this.scope = scope;
        }
    }
    
    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input_sw_5656.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int T = Integer.parseInt(br.readLine());
        for(int tc=1; tc<=T; tc++) {
            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];
            
            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());
                }
            }
            
            ans = Integer.MAX_VALUE; 
            // W에 N개의 구슬을 떨어트리는 중복 순열
            go(0, map);
            sb.append("#").append(tc).append(" ").append(ans).append("\n");
        }
        
        System.out.print(sb.toString());
        br.close();
    }
    
    static boolean go(int count, int[][] map) {
        int remain = getRemain(map);
        
        if(remain==0) {        // 모든 벽돌이 부서졌다면
            ans = 0;
            return true;
        }
        
        if(count==N) {        // 모든 구슬을 던졌다면
            ans = Math.min(ans, remain);
            return false;
        }
        
        int[][] newMap = new int[H][W];
        for(int c=0; c<W; c++) {
            // 블록이 있는 위치 찾기
            int r=0;
            while(r<H && map[r][c]==0) r++;
            if(r==H) continue;        // 깰 블록이 없음, 다음 열로 이동
            
            copy(map, newMap);        // 현재 상태 백업
            boom(r, c, newMap);        // r, c 위치에 구슬 떨어트림
            down(newMap);            // 공중에 떠 있는 블록 아래로 이동
            if(go(count+1, newMap)) return true;        // 다음 구슬로
        }
        return false;
    }
    
    static void boom(int r, int c, int[][] map) {    // 블록 깨트림
        Queue<Point> que = new LinkedList<>();
        if(map[r][c]>1)
            que.offer(new Point(r, c, map[r][c]));
        
        map[r][c] = 0;
        
        while(!que.isEmpty()) {
            Point p = que.poll();
            
            for(int d=0; d<4; d++) {
                int nr = p.r;
                int nc = p.c;
                
                for(int k=1; k<p.scope; k++) {
                    nr += dr[d];
                    nc += dc[d];
                    
                    if(nr<0 || nr>=H || nc<0 || nc>=W || map[nr][nc]==0) continue;
                    if(map[nr][nc]>1) {
                        que.offer(new Point(nr, nc, map[nr][nc]));
                    }
                    map[nr][nc] = 0;
                }
            }
        }
        
    }
    
    static void down(int[][] map) {        // 공중에 떠있는 벽돌 내리기
        for(int c=0; c<W; c++) {
            int r=H-1;
            while(r>0) {
                if(map[r][c]==0) {        // 빈칸이라면 내릴 벽돌 찾기
                    int nr = r-1;
                    while(nr>0 && map[nr][c]==0) nr--;
                    map[r][c] = map[nr][c];
                    map[nr][c] = 0;
                }
                r--;
            }
        }
    }
    
    static int getRemain(int[][] map) {        // 남은 벽돌 수 리턴
        int total=0;
        for(int i=0; i<H; i++) {
            for(int j=0; j<W; j++) {
                if(map[i][j] > 0)
                    total++;
            }
        }
        
        return total;
    }
    
    static void copy(int[][] map, int[][] newMap) {
        for(int i=0; i<H; i++) {
            for(int j=0; j<W; j++)
                newMap[i][j] = map[i][j];
        }
    }
 
}
 

 

📌 채점 결과