백준 11559. Puyo Puyo :: 돼지개발자

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

"BFS를 활용한 구현"

먼저 뿌요뿌요의 실행 순서를 보자.

1. 중력에 의해 모든 뿌요들이 밑으로 떨어진다.

2. 상하좌우로 4개 이상 인접한 같은 색깔의 뿌요들은 모두 동시에 터진다.

간단히 두개의 과정으로 나타낼 수 있다. 이를 구현해주면 끝. 먼저 뿌요들을 밑으로 내리는 코드를 보면 아래와 같다.

for (int i = 11; i >=0 ; i--) {
    for (int j = 0; j < 6; j++) {
        if(map[i][j] == '.') 
            continue;
        
        int nx = i;
        char mark = map[i][j];
        map[i][j] = '.';
        while(true) {
            if(!isRange(nx+1, j) || map[nx+1][j] != '.') 
                break;
            nx++;
        }
        map[nx][j] = mark;
    }
}

그 후 모든 뿌요에서 인접한 같은 뿌요가 4개 이상인 경우를 탐색한다. 이 과정에서 4개 이상의 뿌요들이 인접해 있을 경우, 이를 터트리기 위해 좌표를 기억해두어야 하는데, 이 해답에서는 ArrayList를 사용했다. 같은색의 인접한 뿌요를 탐색할 때마다 뿌요의 좌표를 리스트에 넣고, 

그 개수가 4 이상이라면, 리스트에 담긴 좌표의 뿌요들을 모두 터트려주었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
 
class Main {
 
    static char[][] map = new char[12][6];
    static Queue<Node> q = new LinkedList<>();
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    static boolean[][] visited;
    static ArrayList<Node> list = new ArrayList<>();
    public static void main (String[] args) throws IOException     {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        for (int i = 0; i < 12; i++) {
            map[i] = br.readLine().toCharArray();
        }
        
        int res = 0;
        while(true) {
            boolean finish = true;
            down();
            for (int i = 0; i < 12; i++) {
                for (int j = 0; j < 6; j++) {
                    if(map[i][j] == '.') continue;
                    visited = new boolean[12][6];
                    visited[i][j] = true;
                    int cnt = 0;
                    q.add(new Node(i, j));
                    
                    while(!q.isEmpty()) {
                        
                        Node cur = q.poll();
                        cnt++;
                        list.add(cur);
                        for (int k = 0; k < 4; k++) {
                            int nx = cur.x + dx[k];
                            int ny = cur.y + dy[k];
                            
                            if(!isRange(nx, ny) || visited[nx][ny] || map[nx][ny] != map[cur.x][cur.y])
                                continue;
                            
                            visited[nx][ny] = true;
                            q.add(new Node(nx, ny));
                        }
                    }
                    
                    if(cnt >= 4) {
                        for(Node node : list) {
                            map[node.x][node.y] = '.';
                        }
                        finish = false;
                    }
                    list.clear();
                }
            }
            
            if(finish) break;
            res++;
        }
        System.out.println(res);
    }
    
    static void down() {
        for (int i = 11; i >=0 ; i--) {
            for (int j = 0; j < 6; j++) {
                if(map[i][j] == '.') 
                    continue;
                
                int nx = i;
                char mark = map[i][j];
                map[i][j] = '.';
                while(true) {
                    if(!isRange(nx+1, j) || map[nx+1][j] != '.') 
                        break;
                    nx++;
                }
                map[nx][j] = mark;
            }
        }
    }
    
    static boolean isRange(int x,int y) {
        if( x < 0 || x >= 12 || y < 0 || y >= 6) return false;
        return true;
    }
 
}
 
class Node {
    int x;
    int y;
    
    Node (int x, int y) {
        this.x = x;
        this.y = y;
    }
}