이번에 풀어본 문제는
프로그래머스 프렌즈4블록 입니다.

📕 문제 링크

❗️코드

import java.util.*;
class Block {
    int x, y;

    public Block(int x, int y) {
        this.x = x;
        this.y = y;
    }

}
class Solution {
    static int[] dx = {0, 0, 1, 1};
    static int[] dy = {0, 1, 1, 0};
    static int M, N;
    static char[][] map;
    static boolean[][] isVisited;
    static int answer;
    public int solution(int m, int n, String[] board) {
        M = m;
        N = n;
        map = new char[M][N];
        for (int i = 0; i < M; i++) {
            map[i] = board[i].toCharArray();
        }

        while (boom()) {
            down();
        }
        return answer;
    }
    static void down() {
        for (int i = 0; i < N; i++) {
            for (int j = M -1; j >= 0; j--) {
                if (map[j][i] == '.') {
                    for (int k = j; k >= 0; k--) {
                        if (map[k][i] != '.') {
                            char tmp = map[k][i];
                            map[k][i] = map[j][i];
                            map[j][i] = tmp;
                            break;
                        }
                    }
                }
            }
        }
    }
    static boolean boom() {
        isVisited = new boolean[M][N];
        List<Block> list = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (isBlock(i, j, map[i][j])) {
                    list.add(new Block(i, j));
                }
            }
        }

        int cnt = 0;
        for (Block block : list) {
            for (int idx = 0; idx < 4; idx++) {
                int mx = block.x + dx[idx];
                int my = block.y + dy[idx];

                if (map[mx][my] != '.') {
                    map[mx][my] = '.';
                    cnt++;
                }
            }
        }
        answer += cnt;
        return cnt > 0;
    }

    static boolean isBlock(int x, int y, char name) {
        for (int idx = 0; idx < 4; idx++) {
            int mx = x + dx[idx];
            int my = y + dy[idx];

            if (!isValid(mx, my) || map[mx][my] != name) return false;
        }
        return true;
    }

    static boolean isValid(int x, int y) {
        return x >= 0 && y >= 0 && x < M && y < N;
    }
}

📝 풀이

게임판에서 2x2 크기의 사각형이 만들어지면 터뜨리고, 빈공간은 위에서 떨어져서 채우는 행위를 반복하는 게임을 구현하는 문제입니다.
겹쳐서도 터뜨릴 수 있기 때문에, 미리 터뜨리지 않고 하나의 인덱스를 기준으로 2x2의 사각형을 만들 수 있으면 리스트에 담아두고, 동시에 터뜨리도록 구현했습니다. 터뜨릴 수 있는 블록이 남아있다면 터뜨리고 빈 공간을 채우며, 그렇지 않다면 반복이 종료됩니다.

📜 후기

동일한 블록이 인접하여 크기가 4 이상이면 터뜨리는 줄 알고, 보자마자 그래프탐색을 적용했는데, 정확히 사각형이라 구현하기 조금 깐깐했던 것 같습니다. 복잡하지만 해결해서 다행입니다 ㅎㅎ