문제 접근

블록들 중 2*2 사각형이 같은 모양이라면, 다음 턴에 제거하고, 그 위에 있는 블록들을 그대로 아래로 떨어트리는 시뮬레이션 문제임.

시뮬레이션 문제 특징 답게 n,m이 최대 30으로 매우 작은 범위로 주어짐.

떨어트리는 문제이기 때문에, 문제의 구조를 다른 관점으로 바라봐야함. 기존 배열 읽는 것처럼 읽지 말고, 열 기준으로 바닥부터 위로 올라가면서 이걸 하나의 배열로 바라보는게 쉬움.

절차는 다음과 같이 수행

• 2*2 이어진 블록 구조가 나올 때마다 체크를 해둠.
• 다시 순회를 하면서 체크 표시안한 블록들만 새로 담은 리스트를 만들고, 기존 리스트에서 교체하기

  여기서, 새 리스트를 만들지 않고 기존 리스트를 활용해서 교체하는 식으로 해도 됨. 하지만, 배열 크기가 크지 않고, Block객체는 재활용하기 때문에 사실상 ArrayList tmp를 새로 할당하는 시간과 공간만 소모됨. 드랍하면서 교체하는 방식으로 할 경우 코드가 더 길어지고, 시간적으로 큰 이점이 있다고 생각하지 않아서 이렇게 구현함.

문제 풀이

import java.util.*;

class Solution {
    public int solution(int m, int n, String[] board) {
        int answer = 0;
        ArrayList<Block>[] game = new ArrayList[n];
        for(int j=0; j<n; j++) {
            game[j] = new ArrayList();
            for(int i=m-1; i>=0; i--) {
                char c = board[i].charAt(j);
                game[j].add(new Block(c));
            }
        }
        
        while(true) {
            int remove = 0;
            for(int i=0; i<n-1; i++) {
                if (game[i].size() <= 1) continue;
                Block prev = game[i].get(0);
                for(int j=1; j<game[i].size(); j++) {
                    Block cur = game[i].get(j);
                    if (prev.c == cur.c) {
                        if (game[i+1].size() > j) {
                            Block under1 = game[i+1].get(j-1);
                            Block under2 = game[i+1].get(j);
                            if (under1.c == cur.c && under2.c == cur.c) {
                                prev.checked = true;
                                cur.checked = true;
                            
                                under1.checked = true;
                                under2.checked = true;
                            }
                        }
                    }
                    prev = cur;
                }
            }
            
            for(int i=0; i<n; i++) {
                ArrayList<Block> tmp = new ArrayList();
                for(int j=0; j<game[i].size(); j++) {
                    Block b = game[i].get(j);
                    if (b.checked) {
                        remove++;
                    } else {
                        tmp.add(b);
                    }
                }
                game[i] = tmp;
            }
            
            if (remove == 0) break;
            answer+=remove;
        }        
        
        return answer;
    }
}

class Block {
    final char c;
    boolean checked = false;
    Block(char c) {
        this.c = c;
    }
}