[프로그래머스] 블록 게임

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/42894

문제 풀이

• 구현 문제이다.

• 우선, 각 블록에 대해 모양을 특정하는 건 복잡하므로 특정 블록을 감싸는 직사각형의 ROW, COL 범위를 해당 블록 정보로 저장해주었다. (이하 블록 정보)

• 또한, 위에서 검은 블록을 떨어뜨린다는 가정하에 아래 그림처럼 칼럼 별로 비어있지 않은 최상단 블록의 번호 정보를 저장하는 배열을 만들어 주었다. (이하 상단 경계 배열)
  

• 다음 로직을 더이상 지워지는 블록이 없을 때까지 반복한다.
  - 모든 칼럼값에 대해 다음로직을 반복한다.
  - 현재 칼럼의 상단 경계 배열 값에 해당하는 블록에 대해 다음 판별
  - 해당 블록을 삭제할 수 있는지 없는지 (ROW, COL 범위와 상단 경계 배열 정보 활용)
  - 삭제 가능하면) 보드에서 모두 0으로 만들고, COL범위에 해당하는 상단 경계 배열값 최신화 시켜줌
  - 삭제 불가능하면) 다음 칼럼으로 넘어감

소스 코드 (JAVA)

import java.util.*;

class Solution {

    public class Block {
        int sx, ex, sy, ey;

        public Block (int sx, int ex, int sy, int ey) {
            this.sx = sx;
            this.ex = ex;
            this.sy = sy;
            this.ey = ey;
        }
    }

    public int N;

    public int solution(int[][] board) {
        //초기화
        N = board.length;
        Block[] blocks;

        //blocks 초기화
        int blockCnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++)
                blockCnt = Math.max(blockCnt, board[i][j]);
        }
        blocks = new Block[blockCnt + 1];
        for (int i = 0; i < blockCnt + 1; i++)
            blocks[i] = new Block(50, -1, 50, -1);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int cur = board[i][j];
                if (cur == 0) continue;
                blocks[cur].sx = Math.min(blocks[cur].sx, i);
                blocks[cur].ex = Math.max(blocks[cur].ex, i);
                blocks[cur].sy = Math.min(blocks[cur].sy, j);
                blocks[cur].ey = Math.max(blocks[cur].ey, j);
            }
        }

        //시뮬레이션 시작
        //상단 경계 초기화
        int[] bounds = new int[N];
        Arrays.fill(bounds, -1);
        for (int j = 0; j < N; j++) {
            for (int i = 0; i < N; i++) {
                if (board[i][j] == 0) continue;
                bounds[j] = i;
                break;
            }
            if (bounds[j] == -1)
                bounds[j] = N;
        }

        int result = 0;
        while(true) {
            boolean breakFlag = false;  //부신 벽돌이 있으면 true;

            for (int ind = 0; ind < N; ind++) {
                //부실 수 있는지 판별할 블록
                if (bounds[ind] == N) continue;
                int cur = board[bounds[ind]][ind];

                boolean endFlag = false;
                for (int i = blocks[cur].sx; i <= blocks[cur].ex; i++) {
                    for (int j = blocks[cur].sy; j <= blocks[cur].ey; j++) {
                        //1. 현재 번호의 블록일 경우
                        if (board[i][j] == cur) continue;
                        //2. 빈 칸이며 흑돌이 들어올 수 있는 경우
                        if (board[i][j] == 0 && bounds[j] > i) continue;
                        //3. 이 외의 경우 흑돌을 체울 수 없는 경우
                        endFlag = true;
                        break;
                    }
                    if (endFlag) break;
                }
                if (endFlag) continue;

                //블록을 없앨 수 있는 경우
                result++;
                breakFlag = true;

                //1. 블록 모두 없애주기
                for (int i = blocks[cur].sx; i <= blocks[cur].ex; i++) {
                    for (int j = blocks[cur].sy; j <= blocks[cur].ey; j++) {
                        if (board[i][j] == cur)
                            board[i][j] = 0;
                    }
                }
                //2. 경계 내려주기
                for (int j = blocks[cur].sy; j <= blocks[cur].ey; j++) {
                    bounds[j] = -1;
                    for (int i = 0; i < N; i++) {
                        if (board[i][j] == 0) continue;
                        bounds[j] = i;
                        break;
                    }
                    if (bounds[j] == -1)
                        bounds[j] = N;
                }
            }

            if (!breakFlag) break;
        }
        return result;
    }
}