[SWEA] 5656.벽돌 깨기(시뮬레이션, 완탐).java

#. Problem

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

* The copyright in this matter is in SWEA

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

모든 열(2 ≤ W ≤ 12)에 구슬을 던져보아야 하는데,

구슬은 1 ≤ N ≤ 4 개 던질 수 있다.

그렇다면 W개의 열에 N번의 구슬을 각각 던져보아야 하므로

O(W^N) = 12^4 = 20,736 으로 충분히 해결할 수 있다.

이 문제도 시뮬레이션 문제이므로 조건을 잘 살펴보고

동작의 흐름을 정리해보자.

***

1. 구슬 떨어뜨리기

   (구슬은 좌, 우로만 움직일 수 있어서 항상 맨 위에 있는 벽돌만 깨트릴 수 있다.)

2. 벽돌은 숫자 1 ~ 9 로 표현되며, 구술이 명중한 벽돌은 상하좌우로 ( 벽돌에 적힌 숫자 - 1 ) 칸 만큼 같이 제거

   (구슬의 영향을 받은 벽돌 깨뜨리기)

3. 제거되는 범위 내에 있는 벽돌은 동시에 제거

4. 빈 공간이 있으면 벽돌은 밑으로 떨어지게 된다.

result. 남은 벽돌의 개수 구하기

***

+

2차원 배열 시뮬레이션 문제에서 index를 자유자재로 다루기 아직은 헷갈리다..

이 문제도 나중에 다시 풀어봐야지!

2차원 배열에서 값들을 한 방향으로 당기는 코드는

아래와 같이 index를 활용해서 할 수도 있지만,

    private 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--;
            }
        }
        
    }

List를 활용한 방법은 덜 헷갈리고 유용한 것 같다.

index를 활용하는 방법보다 메모리가 더 들긴 하지만 

그래도 안전하고(?) 빠르게 구현할 수 있다.

배열에 값이 들어있다면 list에 넣고 비워준 후,

당길 방향에 차곡차곡 쌓아주면 된다.

    static ArrayList<Integer> list = new ArrayList<>();
    private static void down(int[][] map) {
        
        for (int c = 0; c < W; c++) {
            
            int r;
            for (r = H - 1; r >= 0; r--) {
                // 벽돌이라면 list에 추가 후 빈 공간으로
                if(map[r][c] > 0) {
                    list.add(map[r][c]);
                    map[r][c] = 0;
                }
            }
            r = H;
            for (int b : list) {
                map[--r][c] = b;
            }
            list.clear();
        }
        
    }

#. Code_bfs

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Solution5656 {
 
    static int N, W, H, res;
    static int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1};
    static class State {
        int r, c, cnt;
 
        public State(int r, int c, int cnt) {
            this.r = r;
            this.c = c;
            this.cnt = cnt;
        }
        
    }
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
 
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken()); // 쏠 수 있는 구슬 개수
            W = Integer.parseInt(st.nextToken());
            H = Integer.parseInt(st.nextToken());
            
            int total = 0;    // 전체 벽돌 개수
            int[][] map = new int[H][W];
            for (int r = 0; r < H; r++) {
                st = new StringTokenizer(br.readLine());
 
                for (int c = 0; c < W; c++) {
                    map[r][c] = Integer.parseInt(st.nextToken());
                    if(map[r][c] > 0) total++;
                }
            }
            
            res = Integer.MAX_VALUE;
            process(0, total, map);
 
            System.out.println("#" + tc + " " + res);
        }
 
    }
 
    private static boolean process(int cnt, int remain, int[][] map) {
        
        // 남은 벽돌의 개수 확인
        if(remain == 0) {
            res = 0;
            // 남은 벽돌이 없다면 더이상 확인할 필요가 없으므로 true
            return true;
        }
        // 던질 수 있는 구슬을 모두 던졌을 경우
        if(cnt == N) {
            res = Math.min(res, remain);
            // 다른 경우도 확인해보아야 하므로 false
            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;
            // 벽돌이 없을 경우 pass
            if(r == H) continue;
 
            // 벽돌이 있을 경우    
            // 이전 구슬의 상태를 복사
            copy(map, newMap);
            // 해당 좌표로 구슬을 떨어뜨려서 벽돌 터뜨리기
            int burstCnt = burst(newMap, r, c);
            // 벽돌 내리기
            down(newMap); 
            // 다음 구슬 처리 (더이상 확인할 필요가 없다면 true)
            if(process(cnt + 1, remain - burstCnt, newMap)) return true;
        }
        
        return false; 
    }
 
    private 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--;
            }
        }
        
    }
 
    private static int burst(int[][] map, int r, int c) {
        
        int cnt = 0;
        Queue<State> q = new LinkedList<>();
        // 벽돌의 숫자가 1보다 크면 queue에 추가
        if(map[r][c] > 1) q.add(new State(r, c, map[r][c]));
        // 벽돌이 깨지면 0
        map[r][c] = 0;
        cnt++;
        
        while(!q.isEmpty()) {
            
            State now = q.poll();
                        
            for (int d = 0; d < 4; d++) {
                int rr = now.r;
                int cc = now.c;
                // (벽돌에 적힌 숫자 - 1) 만큼 영향
                for (int k = 0; k < now.cnt - 1; k++) {
                    rr += dr[d];
                    cc += dc[d];
                    // 범위 확인
                    if(rr < 0 || rr >= H || cc < 0 || cc >= W || map[rr][cc] == 0) continue;
                    if(map[rr][cc] > 1) q.add(new State(rr, cc, map[rr][cc]));
                    
                    map[rr][cc] = 0;
                    cnt++;
                }
            }
        }
        
        return cnt;
    }
 
    private 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];
            }
        }
        
    }
 
}

line 72~89) 1. 모든 열에 구슬을 떨어뜨려보기

line 76) 항상 맨 위에 있는 벽돌만 깨뜨릴 수 있으므로 맨 위 벽돌의 위치를 찾아주어야 한다.

line 117~149) 벽돌이 연쇄적으로 깨지는 과정

line 122) 최초 구슬을 맞은 벽돌의 좌표가 queue에 추가되고

line 135~144) 상하좌우 방향으로 벽돌에 적힌 숫자 - 1 만큼 영향을 받고 queue에 추가

line 142) queue에 추가되면서 벽돌도 부숴주자

line 143) 부서진 벽돌의 개수 count

line 94~115) 빈 공간이 있다면 벽돌을 떨어뜨려주자.

line 58~62) 남은 벽돌의 개수가 0개라면 더이상 확인할 필요가 없음

line 64~68) 던질 수 있는 구슬을 모두 던졌을 경우 남은 벽돌의 개수를 갱신

#. Code_dfs

벽돌이 연쇄적으로 부서지는 과정을 dfs로 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Solution5656_dfs {
 
    static int N, W, H, res, burstCnt;
    static int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1};
    static class State {
        int r, c, cnt;
 
        public State(int r, int c, int cnt) {
            this.r = r;
            this.c = c;
            this.cnt = cnt;
        }
        
    }
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
 
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken()); // 쏠 수 있는 구슬 개수
            W = Integer.parseInt(st.nextToken());
            H = Integer.parseInt(st.nextToken());
            
            int total = 0;    // 전체 벽돌 개수
            int[][] map = new int[H][W];
            for (int r = 0; r < H; r++) {
                st = new StringTokenizer(br.readLine());
 
                for (int c = 0; c < W; c++) {
                    map[r][c] = Integer.parseInt(st.nextToken());
                    if(map[r][c] > 0) total++;
                }
            }
            
            res = Integer.MAX_VALUE;
            process(0, total, map);
 
            System.out.println("#" + tc + " " + res);
        }
 
    }
 
    private static boolean process(int cnt, int remain, int[][] map) {
        
        // 남은 벽돌의 개수 확인
        if(remain == 0) {
            res = 0;
            // 남은 벽돌이 없다면 더이상 확인할 필요가 없으므로 true
            return true;
        }
        // 던질 수 있는 구슬을 모두 던졌을 경우
        if(cnt == N) {
            res = Math.min(res, remain);
            // 다른 경우도 확인해보아야 하므로 false
            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;
            // 벽돌이 없을 경우 pass
            if(r == H) continue;
 
            // 벽돌이 있을 경우    
            // 이전 구슬의 상태를 복사
            copy(map, newMap);
            // 해당 좌표로 구슬을 떨어뜨려서 벽돌 터뜨리기
            burstCnt = 0;
            burst(newMap, r, c, newMap[r][c]);
            // 벽돌 내리기
            down(newMap); 
            // 다음 구슬 처리 (더이상 확인할 필요가 없다면 true)
            if(process(cnt + 1, remain - burstCnt, newMap)) return true;
        }
        
        return false; 
    }
 
    private 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--;
            }
        }
        
    }
 
    private static void burst(int[][] map, int r, int c, int cnt) {
 
        // 벽돌이 깨지면 0
        map[r][c] = 0;
        burstCnt++;
        // 벽돌의 숫자가 1이면 return
        if(cnt == 1) return;
                        
        for (int d = 0; d < 4; d++) {
            int rr = r;
            int cc = c;
            
            // (벽돌에 적힌 숫자 - 1) 만큼 영향
            for (int k = 0; k < cnt - 1; k++) {
                rr += dr[d];
                cc += dc[d];
                // 범위 확인
                if(rr < 0 || rr >= H || cc < 0 || cc >= W || map[rr][cc] == 0) continue;
                burst(map, rr, cc, map[rr][cc]);
            }
        }
        
    }
 
    private 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];
            }
        }
        
    }
 
}

bfs와 유사하지만 부서진 벽돌의 개수를 count 하기 위해

burstCnt는 전역변수로 선언돼야 한다.

(당연히 burst() 함수가 최초로 호출되기 전 burstCnt는 0으로 초기화해줄 것!)

line 121.처럼 visited 상태 처리는 dfs에 들어오자마자 해주는게 좋다.

그렇지 않으면 최초로 dfs() 함수를 호출하기 전에 체크해주고,

재귀 함수를 다시 호출할 때 또 체크해주어야 하는 번거로움(?)이 있다.