[BOJ] 백준 11559. 뿌요뿌요

문제

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

---

풀이

bfs가 포함된 빡 구현 문제이다.
 
 제거할 뿌요를 bfs로 찾고, 삭제하고, 중력을 통해 재 정렬을 해야한다. 여러 그룹의 삭제될 뿌요가 한 텀에 있어도 연쇄는 한 번이라는 것을 잊으면 안된다.
 
 여기서 연속된 4개 이상이 연결된 뿌요를 찾아 제거해야하는데, 그냥 BFS를 사용해 탐색하면, ㅓ ㅏ ㅗ ㅜ 모양의 탐색은 visited에 걸려 탐색을 할 수가 없다. 이것은 단순하게 해결 가능한데, 최대 2번까지 방문을 허용하기만 하면 ㅓ ㅏ ㅗ ㅜ 탐색이 가능하게 된다.
 
중력에 의한 재정렬은 stack을 이용해 구현했다. 제거할 뿌요를 제외한 값을 stack에 push하고, 다시 map[][]의 아래부터 stack에서 pop을 하며 값을 채워넣었다.

코드를 보는 것이 더 이해가 쉬울 것 같다. 아래는 소스 코드이다.

---

소스 코드

import java.util.*;

public class B11559_뿌요뿌요 {
    static char[][] map;
    static int[][] visited;
    static int[] dr = {-1,1,0,0};
    static int[] dc = {0,0,-1,1};
    static ArrayList<int[]> targets;
    static boolean stop = true;
    static int combo = 0;

    public static void main(String[] args) {
        input();
        while(true){
            findTargetAndBlast();
            dropPuyo();
            if(stop) break;
            combo++;
        }
        System.out.println(combo);
    }

    static void input(){
        Scanner sc = new Scanner(System.in);
        map = new char[12][6];
        for(int r=0;r<12;r++){
            String str = sc.next();
            for(int c=0;c<6;c++){
                map[r][c] = str.charAt(c);
            }
        }
    }
    
    static void findTargetAndBlast(){
        stop = true;
        for(int r=0;r<12;r++){
            for(int c=0;c<6;c++){
                if(map[r][c]!='.'){
                    visited = new int[12][6];
                    visited[r][c] = 1;
                    int cnt = bfs(r,c,map[r][c]);
                    if(cnt>=4){
                        stop = false;
                        blastPuyo();
                    }
                }
            }
        }
    }

    static void blastPuyo(){
        for(int[] target:targets){
            int r = target[0];
            int c = target[1];
            map[r][c] = 'T';
        }
    }

    static void dropPuyo(){
        for(int c=0;c<6;c++){
            Stack<Character> stack = new Stack<>();
            for(int r=0;r<12;r++){
                if(map[r][c]!='T'){
                    stack.push(map[r][c]);
                }
            }
            for(int r=11;r>=0;r--){
                if(!stack.isEmpty()) {
                    map[r][c] = stack.pop();
                }
                else map[r][c] = '.';
            }
        }
    }

    static int bfs(int R, int C, char value){
        Queue<int[]> queue = new ArrayDeque<>();
        targets = new ArrayList<>();

        queue.add(new int[]{R,C});
        targets.add(new int[]{R,C});
        int cnt = 1;
        while(!queue.isEmpty()){
            int[] info = queue.poll();
            int r = info[0];
            int c = info[1];

            for(int d=0;d<4;d++){
                int idr = r+dr[d];
                int idc = c+dc[d];
                if(idr<0||idc<0||idr>=12||idc>=6) continue;
                if(visited[idr][idc]>=2) continue;
                if(map[idr][idc]==value){
                    if(visited[idr][idc]==0) {
                        queue.add(new int[]{idr,idc});
                        cnt++;
                    }
                    else queue.add(new int[]{idr,idc});
                    visited[idr][idc]++;
                    targets.add(new int[]{idr,idc});
                }
            }
        }
        return cnt;
    }
}