[Programmers] [1차] 프렌즈4블록

// bfs로 풀기
// 지워진 블록 아래로 내리기
// 2 <= n, m <= 30

// 1. bfs를 통해 모든 블록 순환해 지워지는 블록 n로 변경
// 1.1 bfs를 돌면서 2*2인지 확인 후 다음 블록 확인
// 1.2 지워지는 블록 리스트에 저장
// 2. 아래로 옮기기

import java.util.Queue;
import java.util.LinkedList;
import java.util.HashSet;
import java.util.Arrays;

class Solution {
    class Node{
        int y, x;
        Node(int y, int x){
            this.y = y;
            this.x = x;
        }
    }
    Queue<Node> q = new LinkedList<>();
    String[][] map;
    boolean[][] check;
    int m, n;
    final int[] dirY = {-1, 0, 1, 0};
    final int[] dirX = {0, 1, 0, -1};
    final int[] checkY = {0, 0, 1, 1}; 
    final int[] checkX = {0, 1, 0, 1}; 
    public int solution(int m, int n, String[] board) {
        int answer = 0;
        map = new String[m][n];
        check = new boolean[m][n];
        this.m = m;
        this.n = n;
        Queue<int[]> bombList = new LinkedList<>();
        
        for(int i = 0; i < m; i++){
            map[i] = board[i].split("");
        }
        // int tmp = 0;

        while(true){
            // if(tmp == 2)
            //     break;
            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++){
                    if(!check[i][j] && !map[i][j].equals("n")){
                        q.add(new Node(i, j));
                        check[i][j] = true;
                        while(!q.isEmpty()){
                            Node node = q.poll();
                            check[node.y][node.x] = true;
                            if(!isOverMap(node.y, node.x)){
                                String point = map[i][j];
                                boolean isBomb = true;
                                for(int k = 1; k < 4; k++){
                                    int compareY = node.y + checkY[k];
                                    int compareX = node.x + checkX[k];
                                    if(!map[compareY][compareX].equals(point)){
                                        isBomb = false;
                                        break;
                                    }
                                }
                                if(isBomb){
                                    for(int k = 0; k < 4; k++){
                                        int compareY = node.y + checkY[k];
                                        int compareX = node.x + checkX[k];
                                        int[] bombPoint = {compareY, compareX};
                                        bombList.add(bombPoint);
                                    }                            
                                }
                            }
                        }
                    }
                }
            }
            
            if(bombList.isEmpty()){
                break;
            }
            while(!bombList.isEmpty()){
                int[] bombPoint = bombList.poll();
                map[bombPoint[0]][bombPoint[1]] = "n";
            }
            System.out.println("");
            downBlock();
            for(int k = 0; k < m; k++){
                Arrays.fill(check[k], false);                
            }
        }

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(map[i][j].equals("n")){
                    answer++;
                }
            }
        }
        return answer;
    }
    
    void downBlock(){
        for(int j = 0; j < n; j++){
            int nonePoint = -1;
            for(int i = m-1; i > -1; i--){
                if(map[i][j].equals("n")){
                    if(nonePoint == -1)
                        nonePoint = i-1;
                    // i가 같다면 none위에 남은 블록이 없는 것임
                    if(nonePoint == i){
                        break;
                    }
                    for(int k = nonePoint; k > -1; k--){
                        if(!map[k][j].equals("n")){
                            map[i][j] = map[k][j];
                            map[k][j] = "n";
                            nonePoint = k - 1;
                            break;
                        }
                    }   
                }
            }   
        }
    }
    
    boolean isOverMap(int y, int x){
        for(int i = 0; i < 4; i++){
            if(y + checkY[i] >= m || x + checkX[i] >= n)
                return true;
        }
        return false;
    }
}

bfs를 이용한 단순 구현문제다.