백준 - 11559 Puyo Puyo(Java)

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

11559번: Puyo Puyo

 

dfs 문제입니다.

 

가로12, 세로6 판에 빈 공간 또는 뿌요뿌요가 주어집니다.

한 위치에서 4방향으로 같은 모양의 뿌요뿌요가 있으면 해당 뿌요뿌요는 연쇄됩니다.

만일 연쇄가 될 수 있는 뿌요뿌요가 많아도 1연쇄로 칩니다.

뿌요뿌요가 연쇄가 되면 위에있던 뿌요들은 중력에 의해 아래로 내려옵니다.

이러한 규칙이 있을 때, 연쇄가 몇번 발생하는지 출력하면 되는 문제입니다.

 

자신 주변의 같은 모양의 뿌요뿌요를 찾는 것은 dfs를 사용하여 네 방향 탐색을 하면 됩니다.

만일 자신을 포함하여 네 개 이상의 같은 모양 뿌요뿌요를 찾을 수 있다면 리스트에 저장했다가 삭제하면 됩니다.

주의해야 할 것은, 한 번에 연쇄가 여러번 발생한다 하더라도 1연쇄 입니다.

 

[구현 코드]

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class Main {
    private static int n, m, cnt;
    private static char[][] puyo;
    private static int[] dx = {-1, 1, 0, 0};
    private static int[] dy = {0, 0, -1, 1};
    private static List<int[]> el;
    private static boolean[][] visited;

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

        n = 12;
        m = 6;

        puyo = new char[n][m];

        // 위에서 부터 쌓을 수 있게 입력의 역으로 값을 채움
        for (int i = n - 1; i >= 0; i--) {
            String input = br.readLine();
            for (int j = 0; j < m; j++) {
                puyo[i][j] = input.charAt(j);
            }
        }

        int ans = 0;
        while (true) {
            int boom = 0; // 터지는 것을 확인
            visited = new boolean[n][m];

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    cnt = 1; // 상하좌우로 자신과 같은 뿌요를 찾아 그 개수를 저장
                    el = new ArrayList<>(); // 삭제할 뿌요의 위치 저장

                    // 현재 위치에서 삭제할 수 있는 뿌요가 있는지 확인
                    if (puyo[i][j] == '.') continue;
                    dfs(i, j, puyo[i][j], new ArrayList<>());

                    // 삭제할 뿌요가 있다면 제거
                    if(deleteEl(i, j)) boom++;
                }
            }

            if (boom > 0) {
                /*
                * 뿌요는 중력의 영향을 받아 바닥으로 내려가야 하기 때문에,
                * 아래로 재배치함
                * */
                reArrange();
                ans++;
            }else{
                break;
            }
        }

        bw.write(String.valueOf(ans));

        bw.flush();
        bw.close();
        br.close();
    }

    private static boolean deleteEl(int i, int j){
        if (el.size() > 0) {
            puyo[i][j] = '.';
            for (int[] re : el) {
                puyo[re[0]][re[1]] = '.';
            }
            return true;
        }
        return false;
    }

    // 뿌요 재배치
    private static void reArrange() {
        for (int i = 0; i < m; i++) {
            for (int k = 0; k < n; k++) {
                for (int j = 0; j < (n - 1); j++) {
                    if (puyo[j][i] == '.' && puyo[j + 1][i] != '.') {
                        puyo[j][i] = puyo[j + 1][i];
                        puyo[j + 1][i] = '.';
                    }
                }
            }
        }
    }

    // 삭제할 것을 탐색
    private static void dfs(int x, int y, char chr, List<int[]> list) {
        if (cnt >= 4) {
            for (int[] ints : list) {
                el.add(new int[]{ints[0], ints[1]});
            }
        }

        visited[x][y] = true;

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (!(nx >= 0 && ny >= 0 && nx < n && ny < m)) continue;
            if (chr != puyo[nx][ny]) continue;

            if(!visited[nx][ny]) {
                list.add(new int[]{nx, ny});
                cnt++;
                dfs(nx, ny, chr, list);
            }
        }
    }
}