BOJ 11559 Puyo Puyo [Java]

BOJ 11559 Puyo Puyo

1. 문제 링크

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

2. 문제 해설

문제에서 요구하는 구현해야할 기능을 크게 3가지로 나누어보겠다.

1. 터트릴 뿌요를 파악하기 - bfs 메서드
: 같은 색 뿌요가 4개 이상 연속되는 경우를 찾아야한다. bfs, dfs를 이용하면 되겠다는 생각이 들었는데 dfs를 이용하면 ㅗ, ㅜ 같은 모양으로 연속되있는 경우를 처리하기가 까다롭기에 bfs를 이용하기로 결정하였다. 같은 색 뿌요가 연속되는 경우 list에 담아 list의 크기가 4 이상이면 터트릴 수 있고 아닌 경우는 터트릴 수 없는 방식으로 처리하고자 하였다.

2. 뿌요를 터트리기 - explode 메서드
: list에 담겨 있는 뿌요를 빈 칸으로 만들어주면 된다. 간단하다.

3. 뿌요를 터트린 후, 뿌요들을 내려주기 - goDown 메서드
: 첫번째 열, 맨 밑 행의 칸부터 탐색한다. 기준이 되는 칸이 빈 칸이 아니면 내려줄 필요가 없다. 빈 칸이라면 위의 뿌요들을 내려줘야하므로 그 위의 행들을 탐색한다. 그 위의 칸이 빈 칸이면 내려줄 뿌요가 없는 것이므로 넘어간다. 빈 칸이 아니면 기준이 되는 칸에 뿌요 값을 입력해주고, 뿌요가 있던 칸을 빈 칸으로 만들어준다.

위 기능들을 이용하여 어떻게 처리할지 전체적인 흐름을 살펴보자. 밑의 코드의 45~70줄에 관련된 내용이다.
필드의 모든 칸을 돌면서 뿌요가 있는 칸에서 bfs를 해준다. 같은 색의 연속된 뿌요가 4개 이상이면 폭발시켜준다. 필드 전체를 다 돌아보고 폭발한 적이 있으면 연쇄 횟수를 추가해주고 뿌요들을 내려준다. 폭발한 적이 없다면 더 이상 폭발할 것이 없는 것이므로 연쇄를 중단한다.
이 과정에서 주의해야할 것이 2가지 있다. 첫번째는 bfs에 사용하는 vis배열을 매 연쇄마다 초기화해줘야한다. 연쇄마다 필드와 뿌요 상태가 달라지므로 당연히 매번 초기화해줘야한다. 두번째는 bfs를 한번 마무리할 때마다 list를 비워줘야하는 것이다. 이 부분을 놓쳐서 조금 고생하였다. bfs가 끝났을 때 list를 비워주지 않으면 list에 뿌요가 계속 쌓여서 폭발이 일어나지 않아야할 상황에서도 폭발이 일어나게 된다.

3. 코드 보기

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static class Point {
        int r, c;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    static char[][] field;
    static boolean[][] vis;
    static int[] dr = {0, 1, 0, -1};
    static int[] dc = {1, 0, -1, 0};
    static ArrayList<Point> list;
    static int ans = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        field = new char[12][6];
        list = new ArrayList<>();

        for (int i = 0; i < 12; i++) {
            char[] tmp = br.readLine().toCharArray();

            for (int j = 0; j < 6; j++) {
                field[i][j] = tmp[j];
            }
        }

        solve();

        bw.write(Integer.toString(ans));
        br.close();
        bw.close();
    }

    static void solve() {
        while (true) { // 연쇄를 계속 반복
            vis = new boolean[12][6]; // 새로운 연쇄마다 vis 배열을 초기화해야한다
            boolean explosion = false; // 폭발했는지 여부를 표시

            for (int i = 0; i < 12; i++) { // field 를 돌면서 같은 색의 뿌요가 4개 이상 붙어있는지 탐색
                for (int j = 0; j < 6; j++) {
                    if (field[i][j] != '.') {
                        if (bfs(i, j)) { // 같은 색의 뿌요가 4개 이상이면
                            explode(); // 폭발시킨다
                            explosion = true;
                        }

                        list.clear(); // 뿌요를 폭발시켰다면 리스트를 초기화한다
                    }
                }
            }

            if (explosion) { // 폭발을 했다면
                goDown(); // 뿌요들을 떨어트린다
                ans++;
            } else { // 더 이상 폭발할 뿌요가 없으면 탈출
                break;
            }
        }
    }

    static boolean bfs(int r, int c) { // (r,c)에서 시작하여 탐색하면서 같은 색의 연속된 뿌요를 list 에 넣어준다
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(r, c));
        vis[r][c] = true;
        list.add(new Point(r, c));

        while (!q.isEmpty()) {
            Point cur = q.poll();
            char curColor = field[cur.r][cur.c];

            for (int i = 0; i < 4; i++) {
                int nr = cur.r + dr[i];
                int nc = cur.c + dc[i];

                if (nr < 0 || nc < 0 || nr >= 12 || nc >= 6 || curColor != field[nr][nc] || vis[nr][nc]) { // 범위를 벗어나거나, 연속된 색이 아니거나, 이미 방문한 곳이면 넘어감
                    continue;
                }

                q.add(new Point(nr, nc));
                vis[nr][nc] = true;
                list.add(new Point(nr, nc));
            }
        }

        if (list.size() >= 4) { // 같은 색의 연속된 뿌요가 4개 이상이면 참, 아니면 거짓
            return true;
        } else {
            return false;
        }
    }

    static void explode() {
        for (Point cur : list) {
            field[cur.r][cur.c] = '.';
        }
    }

    static void goDown() {
        for (int i = 0; i < 6; i++) { // 열
            for (int j = 11; j > 0; j--) { // 끝 행에서부터 위로 올라가며 탐색
                if (field[j][i] != '.') { // 밑 부분에 빈 칸이 있고 그 위에 뿌요가 있을 경우 내려줘야하므로, 빈 칸이 아닌 경우는 넘어감
                    continue;
                }

                for (int k = j - 1; k >= 0; k--) { // 기준이 되는 칸부터 위로 올라가며 탐색
                    if (field[k][i] == '.') { // 내릴 칸은 빈 칸이면 안된다
                        continue;
                    }

                    field[j][i] = field[k][i];
                    field[k][i] = '.';
                    break;
                }
            }
        }
    }
}