[JAVA] 백준 11559 : 뿌요뿌요

[JAVA] 백준 11559 : 뿌요뿌요

문제

뿌요뿌요 룰대로 필드가 주어졌을 때 콤보가 몇 번인지 구하는 문제

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

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

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

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

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

접근방법

1. 4개 이상 붙어있는 것들을 체크한다.

2. 1에 해당하는 뿌요들을 한 번에 없애고 위에 있는 뿌요들을 내려준다.

3. 위 단계를 4개 이상 붙어있는 것이 없을 때까지 반복한다.

---

1. "4개 이상 붙어있는 것들을 체크한다."

• BFS를 사용해 붙어있는 것들을 체크한다.

• 이 때, 큐를 하나만 사용하면 큐에 있는 것들이 없어지면서(poll) 인접한 배열 원소들을 큐에 넣는 방식이기 때문에, 인접한 원소를 모두 가지고 있을 큐(count_queue)를 하나 더 만든다.

• 즉, 큐에서 poll() 한 원소를 새로운 큐에 offer() 한다.

• 새로운 큐의 개수가 4개 이상인지 체크한다.

private static int count(char alpha){
    Pos cur_pos;
    while(!queue.isEmpty()){
        cur_pos = queue.poll();
        count_queue.offer(cur_pos);
​
        for(int i=0; i<4; i++){
            Pos next_pos = new Pos(cur_pos.r + dr[i], cur_pos.c + dc[i]);
            // 동일한 색이면서 아직 방문하지 않았으면 큐에 삽입
            if(map[next_pos.r][next_pos.c] == alpha && !check[next_pos.r][next_pos.c]){
                check[next_pos.r][next_pos.c] = true;
                queue.offer(next_pos);
            }
        }
    }
​
    // count_queue : 붙어있는 뿌요들의 모임
    return count_queue.size();
}

○ 새로운 큐의 개수가 4개 이상이면 해당 배열 원소를 'd'로 바꿔준다.

2. 1에 해당하는 뿌요들을 한 번에 없애고 위에 있는 뿌요들을 내려준다.

   • 없어질 뿌요 위에 있는 원소들을 하나하나 밑으로 내려준다.

   • 처음에 배열을 (N+2) x (N+2) 로 설정해놓고, 테두리에 '.'로 설정해주었으므로 배열 범위 체크를 따로 해주지 않아도 된다.

   private static void deletePuyo(Pos pos){
       for(int i=pos.r; i>=1; i--)
           map[i][pos.c] = map[i-1][pos.c];
   }

3. 위 단계를 4개 이상 붙어있는 것이 없을 때까지 반복한다.

• 1에서 4개 이상의 뿌요가 붙어있다면 isQuit 변수를 true로 바꿔주고, combo를 증가시키기 전 해당 변수를 확인해 false라면 combo를 증가시키지 않고 while문을 빠져나간다.

소스코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
​
public class Main{
​
    static int dr[] = {1, -1, 0, 0};
    static int dc[] = {0, 0, 1, -1};
​
    static int N = 12;
    static int M = 6;
    static char map[][];
    static boolean check[][];
    static Queue<Pos> queue;
    static Queue<Pos> count_queue;
​
    static class Pos{
        int r;
        int c;
        public Pos(int r, int c) {this.r = r; this.c = c;}
    }
​
    private static int count(char alpha){
        Pos cur_pos;
        while(!queue.isEmpty()){
            cur_pos = queue.poll();
            count_queue.offer(cur_pos);
​
            for(int i=0; i<4; i++){
                Pos next_pos = new Pos(cur_pos.r + dr[i], cur_pos.c + dc[i]);
                // 동일한 색이면서 아직 방문하지 않았으면 큐에 삽입
                if(map[next_pos.r][next_pos.c] == alpha && !check[next_pos.r][next_pos.c]){
                    check[next_pos.r][next_pos.c] = true;
                    queue.offer(next_pos);
                }
            }
        }
​
        // count_queue : 붙어있는 뿌요들의 모임
        return count_queue.size();
    }
​
    private static void deletePuyo(Pos pos){
        for(int i=pos.r; i>=1; i--)
            map[i][pos.c] = map[i-1][pos.c];
    }
​
​
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int combo = 0;
        N = 12;
        M = 6;
​
        map = new char[N+2][M+2];
        check = new boolean[N+2][M+2];
        queue = new LinkedList<>();
        count_queue = new LinkedList<>();
​
        // 초기화 (테두리 설정)
        for(int i=0; i<N+2; i++)
            for(int j=0; j<M+2; j++)
                map[i][j] = '.';
​
        // 맵 설정
        for(int i=1; i<=N; i++){
            String line = sc.nextLine();
            for(int j=1; j<=M; j++)
                map[i][j] = line.charAt(j-1);
        }
​
        boolean isQuit = false;
        while(true){
            isQuit = true;
            for(int i=1; i<=N; i++){
                for(int j=1; j<=M; j++){
                    // 배열이 값이 알파벳이면서 아직 체크하지 않았다면 큐에 넣는다.
                    if(Character.isAlphabetic(map[i][j]) && !check[i][j]){
                        check[i][j] = true;
                        queue.offer(new Pos(i, j));
​
                        // 붙어있는 동일한 색깔의 뿌요의 개수를 구한다.
                        int num = count(map[i][j]);
​
                        if(num >= 4){
                            for(int k=0; k<num; k++){
                                Pos delete = count_queue.poll();
                                map[delete.r][delete.c] = 'd';
                            }
                            // 하나라도 삭제할 게 있으면 while문이 끝나지 않는다.
                            isQuit = false;
                        }
                        count_queue.clear();
                    }
                }
            }
​
            for(int i=1; i<=N; i++)
                for(int j=1; j<=M; j++){
                    if(map[i][j] == 'd')
                        deletePuyo(new Pos(i, j));
                    check[i][j] = false;
                }
                
            if(isQuit)
                break;
​
            ++combo;
        }
        System.out.println(combo);
    }
}