[백준 11559번] JAVA Puyo Puyo

접근 방식 

해당 문제는 구현(implementation) 이다. 

 

문제의 요구사항은

1. 4개 이상 '.'이 아니고, 인접한 문자가 같을 때 연쇄적으로 터지고, 이를 '.' 기록한다.

2. 연쇄적으로 터진 이후, 배열이 재배열 된다. (문자가 있을 경우, 맨 아래까지 내려간다.)

3. 연쇄적인 것들은, 여러개가 터져도 하나로 기록한다. 

 

코드 

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 java.util.StringTokenizer;

public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st = null;

    public static class Puyo {
        public char[][] arr;
        public boolean process = false;

        Puyo(char[][] arr) {
            this.arr = arr;
        }

        public void move() {
            boolean[][] visited = new boolean[12][6];
            move(visited);
        }

        public void draw() {
            for (int i = 0; i < 6; i++) {
                Queue<Character> st = new LinkedList<>();
                for (int j = 11; j >= 0; j--) {
                    if (arr[j][i] != '.') {
                        st.add(arr[j][i]);
                        arr[j][i] = '.';
                    }
                }
                int cur = 11;
                while (!st.isEmpty()) {
                    arr[cur][i] = st.poll();
                    cur--;
                }
            }
        }

        private void move(boolean[][] visited) {
            process = false;
            for (int i = 0; i < 12; i++) {
                for (int j = 0; j < 6; j++) {
                    if (!visited[i][j] && arr[i][j] != '.') {
                        bfs(i, j, visited);
                    }
                }
            }
        }

        private void bfs(int x, int y, boolean[][] visited) {
            visited[x][y] = true;

            int cnt = 1;
            Queue<int[]> q = new LinkedList<>();
            q.add(new int[]{x, y});
            Queue<int[]> draw = new LinkedList<>();
            draw.add(new int[]{x, y});

            while (!q.isEmpty()) {
                int[] temp = q.poll();
                for (int i = 0; i < 4; i++) {
                    int nextX = dx[i] + temp[0];
                    int nextY = dy[i] + temp[1];
                    if (0 <= nextY && nextY < 6 && 0 <= nextX && nextX < 12) {
                        if (!visited[nextX][nextY] && arr[x][y] == arr[nextX][nextY]) {
                            cnt++;
                            visited[nextX][nextY]= true;
                            q.add(new int[]{nextX, nextY});
                            draw.add(new int[]{nextX, nextY});
                        }
                    }
                }
            }
            if (cnt >= 4) {
                process = true;
                while (!draw.isEmpty()) {
                    int[] temp = draw.poll();
                    arr[temp[0]][temp[1]] = '.';
                }
            }
        }

        public boolean process() {
            return process;
        }
    }

    public static void main(String[] args) throws IOException {

        /*
        * 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다.
        이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다.
        R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다.
        입력으로 주어지는 필드는 뿌요들이 전부 아래로 떨어진 뒤의 상태이다. 즉, 뿌요 아래에 빈 칸이 있는 경우는 없다.
        * */
        char[][] arr = new char[12][6];
        for (int i = 0; i < 12; i++) {
            String s = br.readLine();
            for (int j = 0; j < 6; j++) {
                arr[i][j] = s.charAt(j);
            }
        }

        int sum = 0;
        Puyo puyo = new Puyo(arr);
        while (true) {
            puyo.move();
            if (!puyo.process()) break;
            sum++;
            puyo.draw();
        }
        System.out.println(sum);
    }

    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};
}