BOJ 11559 [Puyo Puyo]

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

어릴때 했던 뿌요뿌요가 생각나는 문제입니다. 시뮬레이션 부분이 SWEA 벽돌 깨기와 유사했습니다.

1. BFS를 돌며 인접한 같은 색 뿌요를 찾는다.

2. BFS를 빠져나오면 탐색 완료된, 인접한 같은 색 뿌요의 개수를 저장한다.

3. 4 이상으로 저장된 뿌요를 삭제한다.

4. 뿌요를 하강시킨다.

5. 삭제할 뿌요가 없을 때 까지 1~4 반복

import java.util.*;
class Node {
    public int i, j;
    public char color;
    public Node(int i, int j, char color) {
        this.i = i;
        this.j = j;
        this.color = color;
    }
}
public class Main {
    public static char[][] Map = new char[12][6];
    public static int[][] Visited = new int[12][6];
    public static int[][] d = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public static Queue<Node> q = new LinkedList<Node>();
    public static Queue<Node> q2 = new LinkedList<Node>();
    public static boolean is_bound(int i, int j) {
        return i>=0 && i< 12 && j >= 0 && j < 6;
    }
    public static void Down_puyo() {
        for(int j = 0; j < 6; j++) {
            for(int i = 10; i>= 0; i--) {
                if(Map[i][j] != '.') {
                    int last_index = i;
                    for(int k = i+1; k < 12; k++) {
                        if(Map[k][j] == '.')  {
                            last_index = k;
                        }
                        else
                            break;
                    }
                    if(last_index != i) {
                        Map[last_index][j] = Map[i][j];
                        Map[i][j] = '.';
                    }
                }
            }
        }
    }
    public static int BFS() {
        int result = 0;
        char color = '.';
        while(!q.isEmpty()) {
            Node node = q.poll();
            q2.offer(node);
            color = node.color;
            result++;
            for(int k = 0; k < 4; k++) {
                int next_i = node.i + d[k][0];
                int next_j = node.j + d[k][1];
                if(is_bound(next_i, next_j) && Map[next_i][next_j] == node.color && Visited[next_i][next_j] == 0) {
                    Visited[next_i][next_j] = 1;
                    q.offer(new Node(next_i, next_j, node.color));
                }
            }
        }
        return result;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for(int i = 0; i < 12; i++) {
            String str = sc.nextLine();
            for(int j = 0; j < 6; j++) {
                Map[i][j] = str.charAt(j);
            }
        }
        
        boolean is_end = true;
        int result = 0;
        while (is_end) {
            is_end = false;
            for (int i = 0; i < 12; i++) {
                for (int j = 0; j < 6; j++) {
                    if (Map[i][j] == '.' || Visited[i][j] != 0)
                        continue;
                    q.offer(new Node(i, j, Map[i][j]));
                    Visited[i][j] = 1;
                    int temp = BFS();
                    while (!q2.isEmpty()) {
                        Node node = q2.poll();
                        Visited[node.i][node.j] = temp;
                    }
                }
            }
            for (int i = 0; i < 12; i++) {
                for (int j = 0; j < 6; j++) {
                    if (Map[i][j] == '.')
                        continue;
                    if (Visited[i][j] >= 4) {
                        is_end = true;
                        Map[i][j] = '.';
                    }
                    Visited[i][j] = 0;
                }
            }
            Down_puyo();
            if(is_end) result++;
        }
        System.out.println(result);
    }
}