[SW Expert] [모의 SW 역량테스트] 5656번 벽돌 깨기 (Java)

SW Expert [모의 SW 역량테스트] 5656번 벽돌 깨기 :

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

 

 

정답률 보고 들어갔다가 큰 코 다쳤던 문제이다. dfs와 bfs를 함께 적용해야 한다.

구슬을 N번 쏠 수 있고, 최대한 많은 벽돌을 깨야 하기 때문에 모든 경우의 수를 확인해봐야 한다.

 

전체적인 흐름으로는,

  0. 초기에 Queue에 int[][] map을 담는다.

  1. Queue에서 map을 꺼낸 뒤, 0번째 행부터 우측으로 하나씩 움직이며 구슬을 떨어뜨린다.

  2. 구슬이 떨어진 벽돌을 기준으로 깨질 수 있는 모든 벽돌을 제거한다.

  3. 남아 있는 벽돌들을 밑으로 떨어뜨린다.

  4. Queue에 map을 다시 담는다.

이런 방식으로 1~4번을 N번 반복해주면 된다.

 

 

이번 풀이에는 2개의 클래스와 6개의 함수를 작성했다.

그 중, 메인이 되는 로직은 Node 클래스와 find, pang, dfs, gravity 함수이다.

 

Node 클래스는 int[][] map과 map에 남아 있는 0의 개수를 뜻하는 num이 선언되어 있다.

num을 map과 함께 묶어준 이유는 벽돌이 얼마나 깨졌는지 실시간으로 알기 위함이다.

N번의 실행이 끝난 뒤 Queue에 남아 있는 map을 하나하나 꺼내서 세어보면 시간이 오래 걸릴 듯 하여 map과 함께 묶어주었다.

 

find 함수는 구슬이 떨어지는 곳의 위치를 Index로 반환해준다.

만약 하나의 열에 벽돌이 하나도 없다면 null을 반환한다.

pang 함수는 구슬이 벽돌에 닿은 후 깨질 수 있는 모든 벽돌을 깨뜨린 후 남은 map과 0의 개수인 num을 반환해준다.

pang 함수 안에서는 dfs와 gravity 함수가 사용되었다.

dfs 함수는 구슬이 닿은 벽돌에서 시작하여 깨뜨릴 수 있는 모든 벽돌을 깨뜨리는 함수이다.

while문으로 작성해도 괜찮았겠지만, dfs를 한번 사용해보고 싶어서 dfs로 구현했다.

gravity 함수는 벽돌을 깨뜨린 후 남아 있는 벽돌을 아래로 떨어뜨리는 함수이다.

지난 번 백준 뿌요뿌요를 풀 때 사용했던 방법과 비슷한 방법으로 구현했다.

 

구현해야 하는 것들이 생각보다 많아서 멘붕이 좀 왔지만,

1기능 1함수를 적용해서 생각해보니 빠르게 정리할 수 있었다.

 

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    static int n, w, h, temp, max;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            max = 0;
            temp = 0;
            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++) { // map 입력
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < w; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                    if (map[i][j] == 0) max++;
                }
            }

            solution(map);
            System.out.println("#" + t + " " + ((w * h) - max));
        }
    }

    private static void solution(int[][] map) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(max, map));

        while (n-- > 0) {
            int len = queue.size();
            for (int t = 0; t < len; t++) {
                Node node = queue.poll();

                for (int j = 0; j < w; j++) {
                    Index index = find(node.map, j); // 벽돌이 닿는 위치
                    if (index != null) queue.add(pang(node, index));
                }
            }
        }
    }

    private static Node pang(Node node, Index index) {
        int[][] map = copyOf(node.map);
        temp = node.num;

        dfs(map, index.x, index.y);
        gravity(map);

        if (max < temp) max = temp;
        return new Node(temp, map);
    }

    private static void dfs(int[][] map, int x, int y) { // 벽돌 깨트리기
        int target = map[x][y];

        if (target == 1) {
            map[x][y] = 0;
            temp++;
        } else if (target != 0) {
            map[x][y] = 0;
            temp++;
            for (int i = 0; i < 4; i++) {
                int nx = x, ny = y;
                for (int c = 0; c < target - 1; c++) {
                    nx = nx + dx[i];
                    ny = ny + dy[i];
                    if (isValid(nx, ny))
                        if (map[nx][ny] != 0) dfs(map, nx, ny);
                }
            }
        }
    }

    private static void gravity(int[][] map) { // 벽돌 제거 후 아래로 떨어뜨림
        Stack<Integer> stack = new Stack<>();

        for (int j = 0; j < w; j++) {
            for (int i = 0; i < h; i++) {
                if (map[i][j] != 0) {
                    stack.push(map[i][j]);
                    map[i][j] = 0;
                }
            }
            int index = h - 1;
            while (!stack.isEmpty()) {
                map[index--][j] = stack.pop();
            }

        }
    }

    private static int[][] copyOf(int[][] map) { // map 깊은 복사
        int[][] result = new int[h][w];
        for (int i = 0; i < h; i++) {
            System.arraycopy(map[i], 0, result[i], 0, w);
        }
        return result;
    }

    private static Index find(int[][] map, int j) { // 구슬이 떨어지는 위치 찾아줌
        for (int i = 0; i < h; i++) {
            if (map[i][j] != 0) return new Index(i, j);
        }
        return null;
    }

    private static boolean isValid(int x, int y) {
        if (x < 0 || y < 0 || x >= h || y >= w) return false;
        return true;
    }
}

class Node {
    int num;
    int[][] map;

    public Node(int num, int[][] map) {
        this.num = num;
        this.map = map;
    }
}

class Index {
    int x;
    int y;

    public Index(int x, int y) {
        this.x = x;
        this.y = y;
    }
}