[백준 11559] Puyo Puyo - JAVA

문제 링크: https://www.acmicpc.net/problem/11559

조건

• 필드 내 같은 색 뿌요가 4개 연결 되어 있으면 터진다.
• 현재 필드에 4개 연결되어 있는 뿌요가 여러 곳이면 동시에 터지며 1연쇄로 취급한다.
• 1연쇄가 끝난 후 뿌요들은 중력에 의해 아래로 떨어진다.

접근 방법

처음 접근했을 때는 단순히 Flood Fill Down 로직으로 풀 수 있을 것 같았습니다.

처음 20분 Flood Fill을 DFS로 구현한 후 제 방식이 틀렸다는 것을 인지했습니다.

• DFS로 구현하면 연쇄 반응인 뿌요들과 아닌 뿌요들에 대해 일관되게 처리할 수 없음
• DFS 방식으로 풀면 연쇄 반응인 뿌요들에 대해 터짐 처리하려면 다시 DFS를 수행해야됨

이러한 문제점들을 파악하고 바로 BFS로 전환했습니다.

큐 2개를 놓고
q라는 큐를 BFS용 큐로 사용하고

또 다른 fill이라는 큐는
처음 좌표의 뿌요와 연쇄반응이 일어나는 뿌요들을 저장하는 큐로 사용했습니다.

이렇게 되면
fill의 원소 개수가 4인 경우에만 따로 처리를 해줄 수 있게 됩니다.

메인 메서드에서 while (chain(field))을 통해 chain메서드를 연쇄 단위로 분리했고
chain에서는 연쇄반응이 발생하지 않은 뿌요들만을 BFS로 모두 탐색하고
down메서드를 통해
연쇄 단위로 아래로 떨어지는 로직을 수행하도록 구현했습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;


class Node {
    int y;
    int x;

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

public class Main {
    static final int N = 12;
    static final int M = 6;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, -1, 0, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[][] field = new char[N][M];

        for (int i = 0; i < N; i++) {
            field[i] = br.readLine().toCharArray();
        }

        int count = 0;
        while (chain(field)) {
            count++;
        }

        System.out.println(count);
    }

    private static boolean chain(char[][] field) {
        boolean[][] visited = new boolean[N][M];

        boolean flag = false;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (field[i][j] != '.' && !visited[i][j] && bfs(field, visited, i, j, field[i][j])) {
                    flag = true;
                }
            }
        }

        if (flag) {
            down(field);
            return true;
        }

        return false;
    }

    static boolean bfs (char[][] field, boolean[][] visited, int sy, int sx, char target) {
        ArrayDeque<Node> q = new ArrayDeque<>();
        ArrayDeque<Node> fill = new ArrayDeque<>();
        q.offer(new Node(sy, sx));
        fill.offer(new Node(sy, sx));
        visited[sy][sx] = true;

        Node node;
        while (!q.isEmpty()) {
            node = q.poll();
            int y = node.y;
            int x = node.x;

            for (int d = 0; d < 4; d++) {
                int ny = y + dy[d];
                int nx = x + dx[d];

                if (0 <= ny && ny < N && 0 <= nx && nx < M && !visited[ny][nx] && field[ny][nx] == target) {
                    visited[ny][nx] = true;
                    q.offer(new Node(ny, nx));
                    fill.offer(new Node(ny, nx));
                }
            }
        }

        if (fill.size() < 4) return false;

        while (!fill.isEmpty()) {
            node = fill.poll();
            field[node.y][node.x] = '.';
        }

        return true;
    }

    static void down(char[][] field) {
        for (int col = 0; col < M; col++) {
            int bottom = 11;
            while (bottom >= 0 && field[bottom][col] != '.') {
                bottom--;
            }
            for (int i = bottom-1; i >= 0; i--) {
                if (field[i][col] != '.') {
                    field[bottom][col] = field[i][col];
                    field[i][col] = '.';
                    bottom--;
                }
            }
        }
    }
}