boj 11559 Puyo Puyo

www.acmicpc.net/problem/11559

11559번: Puyo Puyo

같은 색 뿌요가 4개이상 상하좌우 4방향으로 연결되어있으면 터집니다.

뿌요들이 없어지고나서 남은 뿌요들은 아래로 모두 이동시켜줍니다.

그렇게 모인 뿌요들 중 같은 색 뿌요가 4개이상 모이게 되면 다시 터집니다. => 연쇄가 추가됩니다.

이 과정을 뿌요가 터지지 않을때까지 반복하여 몇 연쇄가 일어나는지 출력하는 문제입니다.

 

저의 로직은 다음과 같습니다.

1. 12 * 6 배열을 돌면서 뿌요가 있는 칸이면 bfs로 몇개가 모여있는지 확인

2. 4개이상 모여있으면 모여있는 뿌요들 제거 => 이 때 제거할 뿌요는 ArrayList에 넣었습니다.

3. 제거된 뿌요가 없으면 t - 1를 출력 후 리턴하고 아니면 다음으로 넘어갑니다.

4. 제거된 뿌요로 인해 빈칸을 위의 뿌요들로 채워줍니다. (뿌요들을 아래로 내려줍니다.)

 

3번에서 t - 1을 출력하는 이유는 몇 번 연쇄인지 출력하는 문제인데 t번 턴에서 뿌요가 터지지 않았기 때문입니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static char list[][] = new char[12][6];
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static ArrayList<int[]> erasepoint = new ArrayList<>();
    static boolean visit[][] = new boolean[12][6];
    static int cnt;
 
    static void bfs(int sx, int sy) {
        Deque<int[]> dq = new ArrayDeque<>();
        dq.add(new int[] { sx, sy });
        visit[sx][sy] = true;
        cnt = 0;
        while (!dq.isEmpty()) {
            int x = dq.peek()[0];
            int y = dq.poll()[1];
            erasepoint.add(new int[] { x, y });
            cnt++;
 
            for (int i = 0; i < 4; i++) {
                int nx = x + direct[i][0];
                int ny = y + direct[i][1];
 
                if (nx < 0 || ny < 0 || nx >= 12 || ny >= 6)
                    continue;
                if (visit[nx][ny] || list[nx][ny] != list[x][y])
                    continue;
 
                dq.add(new int[] { nx, ny });
                visit[nx][ny] = true;
            }
        }
    }
 
    static void func() {
        for (int t = 1;; t++) {
            boolean chk = false;
            for (int i = 0; i < 12; i++)
                Arrays.fill(visit[i], false);
 
            for (int i = 0; i < 12; i++) {
                for (int j = 0; j < 6; j++) {
                    if (list[i][j] == '.')
                        continue;
                    bfs(i, j);
                    if (cnt >= 4) {
                        chk = true;
                        for (int xy[] : erasepoint) {
                            list[xy[0]][xy[1]] = '.';
                        }
                    }
                    erasepoint.clear();
                }
            }
 
            if (!chk) {
                System.out.println(t - 1);
                return;
            }
 
            for (int i = 10; i >= 0; i--) {
                for (int j = 0; j < 6; j++) {
                    if (list[i][j] == '.')
                        continue;
 
                    for (int k = i + 1; k < 12; k++) {
                        if (list[k][j] != '.') {
                            char tmp = list[i][j];
                            list[i][j] = list[k - 1][j];
                            list[k - 1][j] = tmp;
                            break;
                        } else {
                            if (k == 11) {
                                char tmp = list[i][j];
                                list[i][j] = list[k][j];
                                list[k][j] = tmp;
                                break;
                            }
                        }
                    }
                }
            }
        }
    }
 
    static void input() throws Exception {
        for (int i = 0; i < 12; i++) {
            st = new StringTokenizer(br.readLine());
            list[i] = st.nextToken().toCharArray();
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}