[백준] 11559: Puyo Puyo - JAVA

21 Jul 2023 in Algorithm on 구현

https://www.acmicpc.net/problem/11559

풀이

같은 색 블럭이 4개 이상 연결되어 있으면 한번에 없어진다.

한 라운드씩 진행하여 없어질 수 있는 블럭이 있으면 1연쇄 늘어나고 다음 라운드로 넘어갔다.

라운드를 넘어가기 전에 블럭들을 없앤 후 밑으로 내려주는 작업도 필요했다.

이차원 배열을 탐색하여 ‘.’이 아닌 경우 bfs탐색을 진행했다.

상하좌우에 같은 색이 있으면 list에 담고 queue에 넣어 계속했다.

list에 담긴 개수가 4이상이면 ‘.’으로 없애주었다.

이번 라운드에 없어진 블럭이 있으면 내려주는 작업을 해야한다.

내려줄때는 열을 먼저 탐색하여 해당 열의 블럭들을 stack에 담아 아래에서부터 채워줬다.

---

메모리: 14480KB

시간: 128ms

언어: Java 11

코드

import java.io.*;
import java.util.*;

public class Main {
    static class Node {
        int r;
        int c;

        public Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    static char[][] board;
    static int ans;

    static int[][] vector = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        board = new char[12][6];
        for (int i = 0; i < 12; i++) {
            board[i] = br.readLine().toCharArray();
        }

        ans = 0;
        playGame();

        System.out.println(ans);
    }

    private static void playGame() {
        boolean isFinished = true;
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 6; j++) {
                if (board[i][j] != '.') {
                    if (bfs(i, j, board[i][j])) {
                        isFinished = false;
                    }
                }
            }
        }

        if (!isFinished) {
            ans++;
            drop();
            playGame();
        }
    }

    private static void drop() {
        for (int i = 0; i < 6; i++) {
            Stack<Character> stack = new Stack<>();
            for (int j = 0; j < 12; j++) {
                if (board[j][i] != '.') {
                    stack.add(board[j][i]);
                }
            }

            int idx = 11;
            while (!stack.isEmpty()) {
                board[idx--][i] = stack.pop();
            }
            for (int j = idx; j >= 0; j--) {
                board[j][i] = '.';
            }
        }
    }

    private static boolean bfs(int r, int c, char color) {
        Queue<Node> queue = new LinkedList<>();
        boolean[][] visit = new boolean[12][6];
        queue.add(new Node(r, c));
        visit[r][c] = true;

        ArrayList<Node> list = new ArrayList<>();
        list.add(new Node(r, c));

        while (!queue.isEmpty()) {
            Node node = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nr = node.r + vector[i][0];
                int nc = node.c + vector[i][1];

                if (nr < 0 || nc < 0 || nr >= 12 || nc >= 6 || visit[nr][nc]) {
                    continue;
                }

                if (board[nr][nc] == color) {
                    queue.add(new Node(nr, nc));
                    list.add(new Node(nr, nc));
                    visit[nr][nc] = true;
                }
            }
        }

        if (list.size() < 4) {
            return false;
        }

        for (Node node : list) {
            board[node.r][node.c] = '.';
        }
        return true;
    }

}