[프로그래머스/LV2] 프렌즈4블록 - 구현(Java)

[2018 KAKAO BLIND RECRUITMENT] [1차] 프렌즈4블록

🙋‍♂️ 들어가며

O(30 * 30 * 30 * 30)

// while true
    // 1-1. boolean 블록이 제거될 것인가?
    // 1-2. boolean[][] visited;
    // 1-3. 최적화 (빈공간 메꿀 영역)
    // bottom_r, sc, ec -> max(r+1), min(c, sc), max(c+1, ec)

    // 2. 4개 블록을 고려해서 행, 열1칸씩 빼고 검사 (만약 다 같으면 true 처리)

    // 3. 블록 제거될 것인가 == false -> break

    // 4. 블록 제거 될 것인가 == true 라면
    // visited == true인 것들 '.'로 변환하고, cnt++

    // 5. 빈공간 메꾸기
    // (시작열 ~ 끝열)에ㅓ bottom_r부터 탐색하는데 '.' 일때
    // 그 좌푤르 기준으로 행은 idx-1부터 0까지 검사해서 알파벳이 나오면
    // 서로 위치 교체하고 break

✅ 코드

class Solution {
    public int solution(int m, int n, String[] board) {
        int cnt = 0;

        int row = m;
        int col = n;
        char[][] arr = new char[row][col];

        for (int r = 0; r < row; r++) {
            String cols = board[r];
            for (int c = 0; c < col; c++) {
                arr[r][c] = cols.charAt(c);
            }
        }



        // 1. 완전탐색 O(30 * 30 * 30 * 30)
        while (true) {
            boolean will_block_be_removed = false;
            boolean[][] visited = new boolean[row][col];

            // 1-1. 최적화 (빈공간 메꿀영역) 
            int bottom_r = Integer.MIN_VALUE;
            int sc = Integer.MAX_VALUE;
            int ec = Integer.MIN_VALUE;

            // 1-2. 2*2블록을 고려해서 전체 행,열 범위 1칸 빼고 빼고 검사
            for (int r = 0; r < row-1; r++) {
                for (int c = 0; c < col-1; c++) {
                    // 1-3. '.' 이면 넘어가기
                    if (arr[r][c] == '.') continue;

                    // 1-4. 알파벳일때
                    char ch = arr[r][c];
                    char right = arr[r][c+1];
                    char diag = arr[r+1][c+1];
                    char down = arr[r+1][c];

                    // 1-5. 만약 4개가 같다면 -> true처리, 빈공간 메꿀 영역 갱신
                    if (ch == right && right == diag && diag == down) {
                        visited[r][c] = true;
                        visited[r][c+1] = true;
                        visited[r+1][c+1] = true;
                        visited[r+1][c] = true;
                        will_block_be_removed = true;

                        bottom_r = Math.max(r+1, bottom_r);
                        sc = Math.min(c, sc);
                        ec = Math.max(c+1, ec);
                    }
                }
            }

            // 1-3. 만약 블록이 제거 안될거라면? -> 종료
            if (!will_block_be_removed) break;

            // 1-4. 블록이 제거 가능하다면? -> true 좌표는 '.' 으로 변경
            for (int r = 0; r < row ; r++) {
                for (int c = 0; c < col; c++) {
                    if (visited[r][c]) {
                        arr[r][c] = '.';
                        cnt++;
                    }
                }
            }

            // 1-5. 빈공간 메꾸기
            for (int cc = sc; cc < ec + 1; cc++) {
                for (int cr = bottom_r; cr >= 0; cr--) {
                    // 1-6. 만약 '.' 이라면
                    if (arr[cr][cc] == '.') {
                        int idx = cr - 1;
                        // 1-7. 위로 올라가면서 알파벳 나오면 위치 교환하고 break
                        while (idx >= 0) {
                            if (arr[idx][cc] != '.') {
                                char temp = arr[idx][cc];
                                arr[cr][cc] = temp;
                                arr[idx][cc] = '.';
                                break;
                            }
                            idx--;
                        }
                    }
                }
            }


        }


        // 2. 결과 반환
        return cnt;
    }
}