[알고리즘] 프렌즈4블록 level2

문제

https://school.programmers.co.kr/learn/courses/30/lessons/17679
문제 파악 -> 빡 구현
1. 2x2 같은 블록 찾기
2x2 모양이 고정되어 있기 때문에 2중 반복문으로 현재위치(x,y)와 (x+1,y)(x,y+1)(x+1,y+1)를 비교해서 같으면 삭제를 해준다. 바로 삭제하는게 아니라 겹쳐서 2x2모양이 나올 수 있으니 boolean배열 타입에 저장해준다.
2. 블록 삭제
위 remove배열에 true인 블록을 지워준다. String은 값을 변하기 어렵기 때문에
char 2차원 배열을 이용해 지워준다.
3. 블록 아래로 떨어지기

이런식으로 세로에 있는값들을 거꾸로 q에 집어넣은다음에
q를 다시 세로에 차례로 집어넣고 나머지는 '#'(빈공간)으로 채워넣는다.

코드

import java.util.*;
class Solution {
    static int[] dx={0,1,0,-1};
    static int[] dy={1,0,-1,0};
    static boolean[][] removed;
    static char[][] map;
    public int solution(int m, int n, String[] board) {
        int answer = 0;
        int x=0,y=0;
        //String보다 char배열값이 값 변하기 좋음
        map=new char[m][n];
        for(int i=0;i<m;i++){
            map[i]=board[i].toCharArray();
        }
        boolean flag=true;
        while(flag){
            removed=new boolean[m][n];
            for(int i=0;i<m-1;i++){
                for(int j=0;j<n-1;j++){
                    if(map[i][j]=='#') continue;
                    
                    if(check(i,j)){

                        removed[i][j]=true;
                        removed[i+1][j]=true;
                        removed[i][j+1]=true;
                        removed[i+1][j+1]=true;
                    }
                    
                }
            }
            int cnt=mapRemove(m,n);
            if(cnt==0) break;
            answer+=cnt;
            }
        return answer;
    }
    //1
    static boolean check(int x,int y){
        char c=map[x][y];
        if(map[x][y+1]==c&&map[x+1][y+1]==c&&map[x+1][y]==c) return true;
        return false;
    }
    //2,3
    static int mapRemove(int m,int n){
        boolean remove=false;
        int cnt=0;
        //2
        for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(removed[i][j]){
                        cnt++;
                        map[i][j]='#';
                    }
                }
             }
         //3
        for(int i=0;i<n;i++){
            Queue<Character> q=new LinkedList<>();
            for(int j=m-1;j>=0;j--){
                if(map[j][i]!='#') q.offer(map[j][i]);
            }
            int index=m-1;
            while(!q.isEmpty()){
                map[index--][i]=q.poll();
            }
            for(int j=index;j>=0;j--){
                map[j][i]='#';
            }
        }
        return cnt;
        
    }
}