[Algo] 백준 11559 Puyo Puyo JAVA

문제 바로가기 : https://www.acmicpc.net/problem/11559

메모리 : 14280KB

시간 : 132ms

언어 : Java 11

---

코드

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

import javax.naming.LinkException;

public class Main {
    static char[][] map;
    static int[][] vector = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } };
    static int ans;

    static class Node {
        int r, c, cnt;

        Node(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));
        map = new char[12][6];
        for (int i = 0; i < 12; i++) {
            String str = br.readLine();
            for (int j = 0; j < 6; j++) {
                map[i][j] = str.charAt(j);
            }
        }
        ans = 0;
        while (true) {
            if (isboom() == 0)
                break;
            ans++;
            down();
        }
        System.out.print(ans);
    }

    private static void down() {
        Queue<Character> tmp = new LinkedList<>();
        for (int j = 0; j < 6; j++) {
            for (int i = 11; i >= 0; i--) {
                if (map[i][j] != '.') {
                    tmp.add(map[i][j]);
                    map[i][j] = '.';
                }
            }
            int idx = 11;
            while (!tmp.isEmpty()) {
                map[idx--][j] = tmp.poll();
            }
        }
    }

    private static int isboom() {
        // 연쇄를 저장할 스택
        Stack<Node> stack = new Stack<>();
        boolean[][] check = new boolean[12][6];
        // 터트릴것이 있나 조사
        for (int i = 11; i >= 0; i--) {
            for (int j = 0; j < 6; j++) {
                if (map[i][j] != '.' && !check[i][j]) {
                    int total = 1;
                    char match = map[i][j];
                    Queue<Node> q = new LinkedList<>();
                    check[i][j] = true;
                    q.add(new Node(i, j, 1));
                    stack.add(new Node(i, j, 1));
                    while (!q.isEmpty()) {
                        Node n = q.poll();
                        for (int k = 0; k < 4; k++) {
                            int x = n.r + vector[k][0];
                            int y = n.c + vector[k][1];
                            if (x < 12 && y < 6 && x >= 0 && y >= 0 && map[x][y] == match && !check[x][y]) {
                                check[x][y] = true;
                                stack.add(new Node(x, y, n.cnt));
                                q.add(new Node(x, y, n.cnt + 1));
                                total++;
                            }
                        }
                    }
                    while (total < 4 && total != 0) {
                        stack.pop();
                        total--;
                    }
                }
            }
        }
        boolean flag = stack.isEmpty() ? false : true;
        // 터트리기
        while (!stack.isEmpty()) {
            Node n = stack.pop();
            map[n.r][n.c] = '.';
        }
        if (flag) {
            return 1;

        } else {
            return 0;
        }
    }

}

풀이

추억의 뿌요뿌요 게임에서 연쇄를 얼마나 쌓을 수 있는지 체크하는 문제이다. 구현문제라고 볼 수 있다. isboom 함수로 4개 이상 인접한 같은 색 뿌요를 터트려준 뒤, down함수로 모든 뿌요를 빈공간없이 밑바닥까지 내려주는 작업을 반복하면 된다. 한 턴에 터트릴 수 있는 뿌요를 모두 터트리는 것이 포인트이기 때문에, 모든 배열을 돌면서 작업을 해주면 된다!