[백준] 11559 Puyo Puyo (자바)

문제

뿌요뿌요의 룰은 다음과 같다.필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.

뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다. 이때 1연쇄가 시작된다.

뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.

아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.

터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.

남규는 최근 뿌요뿌요 게임에 푹 빠졌다. 이 게임은 1:1로 붙는 대전게임이라 잘 쌓는 것도 중요하지만, 상대방이 터뜨린다면 연쇄가 몇 번이 될지 바로 파악할 수 있는 능력도 필요하다. 하지만 아직 실력이 부족하여 남규는 자기 필드에만 신경 쓰기 바쁘다. 상대방의 필드가 주어졌을 때, 연쇄가 몇 번 연속으로 일어날지 계산하여 남규를 도와주자!

 

 

문제풀이

1. for문만 돌아도 되는거 아닌가요?! NONO 터질 수 있는 뿌요들이 여러개라면 동시에 터져야하기 때문에...for문에서 동시에 터질 수 있는 것을 탐색해 준 후 터트려주고 -> 뿌요를 바닥으로 내려주고 -> 다시 탐색해야 한다!

(필자는 동시에 터지는거 생각 안하다 개고생함,,,)

        // 반복적으로 뿌요를 제거하고 중력을 적용
        while (true) {
            flag = false; // flag 초기화
            boolean[][] visited = new boolean[12][6]; // 방문 배열 초기화

            for (int i = 0; i < 12; i++) {
                for (int j = 0; j < 6; j++) {
                    if (board[i][j] != '.' && !visited[i][j]) {
                        bfs(i, j, board[i][j], visited);
                    }
                }
            }

            if (!flag) {
                break; // 더 이상 제거할 뿌요가 없으면 종료
            }
            dropPuyo();
            answer++;
        }

 

bfs 4개 붙은 뿌요들 찾아서 없애주자

    private static void check(int startX, int startY, char ch, boolean[][] visited) {
        Queue<int[]> queue = new LinkedList<>();
        ArrayList<int[]> list = new ArrayList<>();

        queue.offer(new int[]{startX, startY});
        list.add(new int[]{startX, startY});
        visited[startX][startY] = true;

        int count = 1;

        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                if (nx >= 0 && ny >= 0 && nx < 12 && ny < 6 && board[nx][ny] == ch && !visited[nx][ny]) {
                    queue.offer(new int[]{nx, ny});
                    list.add(new int[]{nx, ny});
                    visited[nx][ny] = true;
                    count++;
                }
            }
        }

        if (count >= 4) {
            flag = true;
            for (int[] pos : list) {
                board[pos[0]][pos[1]] = '.';
            }
        }
    }

 

터진 후 뿌요들 drop

    private static void dropPuyo() {
        for (int i = 0; i < 6; i++) { // 각 열에 대해 중력 적용
            Queue<Character> queue = new LinkedList<>();
            for (int j = 11; j >= 0; j--) {
                if (board[j][i] != '.') {
                    queue.offer(board[j][i]);
                }
            }
            for (int j = 11; j >= 0; j--) {
                if (!queue.isEmpty()) {
                    board[j][i] = queue.poll();
                } else {
                    board[j][i] = '.';
                }
            }
        }
    }

 

전체코드

import java.util.*;

public class Main {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static char[][] board = new char[12][6];
    static int answer = 0;
    static boolean flag;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        for (int i = 0; i < 12; i++) {
            String str = in.next();
            for (int j = 0; j < 6; j++) {
                board[i][j] = str.charAt(j);
            }
        }

        // 반복적으로 뿌요를 제거하고 중력을 적용
        while (true) {
            flag = false; // flag 초기화
            boolean[][] visited = new boolean[12][6]; // 방문 배열 초기화

            for (int i = 0; i < 12; i++) {
                for (int j = 0; j < 6; j++) {
                    if (board[i][j] != '.' && !visited[i][j]) {
                        bfs(i, j, board[i][j], visited);
                    }
                }
            }

            if (!flag) {
                break; // 더 이상 제거할 뿌요가 없으면 종료
            }
            dropPuyo();
            answer++;
        }
        System.out.print(answer);
    }

    private static void bfs(int startX, int startY, char ch, boolean[][] visited) {
        Queue<int[]> queue = new LinkedList<>();
        ArrayList<int[]> list = new ArrayList<>();

        queue.offer(new int[]{startX, startY});
        list.add(new int[]{startX, startY});
        visited[startX][startY] = true;

        int count = 1;

        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                if (nx >= 0 && ny >= 0 && nx < 12 && ny < 6 && board[nx][ny] == ch && !visited[nx][ny]) {
                    queue.offer(new int[]{nx, ny});
                    list.add(new int[]{nx, ny});
                    visited[nx][ny] = true;
                    count++;
                }
            }
        }

        if (count >= 4) {
            flag = true;
            for (int[] pos : list) {
                board[pos[0]][pos[1]] = '.';
            }
        }
    }

    private static void dropPuyo() {
        for (int i = 0; i < 6; i++) { // 각 열에 대해 중력 적용
            Queue<Character> queue = new LinkedList<>();
            for (int j = 11; j >= 0; j--) {
                if (board[j][i] != '.') {
                    queue.offer(board[j][i]);
                }
            }
            for (int j = 11; j >= 0; j--) {
                if (!queue.isEmpty()) {
                    board[j][i] = queue.poll();
                } else {
                    board[j][i] = '.';
                }
            }
        }
    }
}