[백준 with Java] 11559번 : Puyo Puyo - 시뮬레이션

 

11559번: Puyo Puyo

 

 

 

 

문제

 

 

 

 

 

 

 

 

문제 접근

주어진 각 색깔 뿌요들의 상하좌우를 봤을 때 연결되어 있는게 각 4개 이상이면 동시에 터진다.

이후 뿌요 아래 빈칸 없이 다 내려온다.

 

이것을 반복하면 되는 문제로 문제 해석은 어렵지 않았습니다.

 

다만 조건과 빈 칸 없이 내려오기 위해서는 없어진 뿌요들을 기록해놔야 함이 번거로운 작업일 거 같았습니다.

 

 

 

 

 

 

시간 복잡도

가로 6

세로 12

사이즈의 2차원 배열을 완전탐색해야 원하는 정답을 구할 수 있습니다.

 

72칸에 최대 뿌요가 터지는 횟수는 대략 72 / 4로 18개라 했을 때

18 * (72칸 에서 * 71칸 검색 * 72칸 중력) < 1억 이므로 충분히 가능합니다.

 

 

 

 

 

 

 

문제 풀이

먼저 뿌요는 무조건 가장 아래에 있습니다.

 

저는 가장 아래를 탐색해서 뿌요가 나올 경우 완전탐색을 진행할 것입니다.

 

이 때 같은 색상으로 인접한 경우와

다른 색상인 경우로 나뉘는데

같은 색상은 곧장 개수를 세지만 다른 색상은 현재 뿌요를 끝마치고 탐색하려고 합니다.

다른 색상의 뿌요도 따로 해당 색상에 맞춰 탐색해야하는 이유는 “동시에" 뿌요가 터질 수 있기 때문입니다.

 

때문에 저는 Queue를 두개 사용해서 현재 탐색과 이후 탐색 예정으로 나눠놨으며

현재 탐색이 터질 수 있는 뿌요일 때 List에 저장해둔 뿌요들을 fields 2차원배열에서 삭제합니다.

 

이제 이후 탐색 예정 Queue를 꺼내서 반복해줍니다.

 

탐색된 부분들은 visited 로 중복 탐색을 피하였으며

가장 아래 탐색이 완료 한 후에 터진 뿌요가 하나라도 있을 때 pang++ 했습니다.

 

이제 지워진 뿌요들이 있고 남은 뿌요 아래 남은 공간들이 있으므로 다 밑으로 내려주고 다시 처음부터 탐색을 시작합니다.

 

만약 지워진 뿌요가 없다면 변화가 없을 것이므로 탐색을 종료하고 정답을 출력합니다.

 

 

 

 

 

Puyo Puyo 코드

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

public class Main {

    static int Y_MAX = 12;
    static int X_MAX = 6;
    static int[] dy = {1, -1, 0, 0}, dx = {0, 0, 1, -1};
    static char[][] fields;
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        visited = new boolean[Y_MAX][X_MAX];
        fields = new char[Y_MAX][X_MAX];

        for (int i = 0; i < Y_MAX; i++) {
            char[] chars = br.readLine().toCharArray();
            for (int j = 0; j < X_MAX; j++) {
                fields[i][j] = chars[j];
            }
        }

        int pang = 0;
        while (true) {
            boolean isPang = false;
            for (int i = 0; i < Y_MAX; i++) Arrays.fill(visited[i], false);

            for (int j = 0; j < X_MAX; j++) {
                if (fields[Y_MAX - 1][j] == '.') continue;
                if (visited[Y_MAX - 1][j]) continue;

                Queue<Point> repo = new LinkedList<>();
                repo.add(new Point(Y_MAX - 1, j));

                while (!repo.isEmpty()) {
                    Point poll = repo.poll();
                    if (visited[poll.y][poll.x]) continue;

                    List<Point> deletedList = new ArrayList<>();
                    Queue<Point> selectedRepo = new LinkedList<>();
                    selectedRepo.add(poll);
                    char selectedColor = fields[poll.y][poll.x];
                    int count = 0;
                    
                    while (!selectedRepo.isEmpty()) {
                        Point selectedPoll = selectedRepo.poll();
                        if (visited[selectedPoll.y][selectedPoll.x]) continue;

                        deletedList.add(selectedPoll);
                        visited[selectedPoll.y][selectedPoll.x] = true;
                        count++;
                        
                        for (int k = 0; k < 4; k++) {
                            int ny = selectedPoll.y + dy[k];
                            int nx = selectedPoll.x + dx[k];

                            if (0 > nx || nx >= X_MAX || 0 > ny || ny >= Y_MAX) continue;
                            if (visited[ny][nx]) continue;

                            if (fields[ny][nx] == selectedColor) {
                                selectedRepo.add(new Point(ny, nx));
                            } else if (fields[ny][nx] != '.') {
                                repo.add(new Point(ny, nx));
                            }
                        }
                    }
                    
                    if (count >= 4) {
                        isPang = true;
                        for (Point deleted : deletedList) fields[deleted.y][deleted.x] = '.';
                    }
                }
            }

            // 중력
            for (int i = 0; i < X_MAX; i++) {
                for (int k = Y_MAX - 1; k >= 0; k--) {
                    if (fields[k][i] == '.') {
                        for (int l = k - 1; l >= 0; l--) {
                            if (fields[l][i] != '.') {
                                fields[k][i] = fields[l][i];
                                fields[l][i] = '.';
                                break;
                            }
                        }
                    }
                }
            }
            if (isPang) pang++;
            if (!isPang) break;
        }
        System.out.println(pang);
    }
}

class Point {
    int y, x;

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