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

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

🙋‍♂️ 들어가며

O(N^4)

이번 문제는 while (true) 동안 일치하는 4개가 있으면 true로 만들고

하나라도 없다면 break로 탈출

만약 1개라도 있다면 전부 .으로 만들고 빈공간 메꾸기

✅ 코드

class Solution {
    public int solution(int m, int n, String[] board) {
        int answer = 0;
        
        // 1. 배열 생성 및 값 할당
        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);
            }
        }
        
        // 2. 블록이 안지워졌다면 종료
        while (true) {
            boolean will_block_be_removed = false;
            boolean[][] visited = new boolean[row][col];
            
            // 최적화 (맨밑에서부터 시작할 행)
            // 시작 열 ~ 끝열
            int bottom_r = -1;
            int sc = Integer.MAX_VALUE;
            int ec = Integer.MIN_VALUE;
            
            // 2-1. 완전탐색
            for (int r = 0; r < row-1; r++) {
                for (int c = 0; c < col-1; c++) {
                    // 2-2. 만약 .이면 넘어가기
                    if (arr[r][c] == '.') continue;
                    
                    // 2-3. .이 아닐때
                    char ch = arr[r][c];
                    char right = arr[r][c+1];
                    char diag = arr[r+1][c+1];
                    char down = arr[r+1][c];
                    
                    // 2-4. 모두 같다면? -> true, 그리고 (블록은 지워질 것 = 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;
                        
                        // 2-5. 갱신 (밑에서부터 시작할 행, 시작열, 끝열)
                        bottom_r = Math.max(bottom_r, r+1);
                        sc = Math.min(c, sc);
                        ec = Math.max(ec, c+1);
                    }
                }
            }
            
            // 2-6. 지울 블럭 없으면 break
            if (!will_block_be_removed) break;
            
            // 2-7. 지울 블럭이 있다면?
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (visited[i][j]) {
                        arr[i][j] = '.';
                        answer++;
                    }
                }
            }
            
            // 3. 빈공간 메꾸기
            for (int cc = sc; cc < ec + 1; cc++) {
                for (int cr = bottom_r; cr >= 0; cr--) {
                    // 3-1. 빈공간일때
                    if (arr[cr][cc] == '.') {
                        // 3-2. 행 한칸 위에서부터 알파벳 찾으면 위치 바꾸고 종료
                        int idx = cr-1;
                        while (idx >= 0) {
                            if (arr[idx][cc] != '.') {
                                char temp = arr[idx][cc];
                                arr[cr][cc] = temp;
                                arr[idx][cc] = '.';
                                break;
                            }
                            idx--;
                        }
                    }
                }
            }
            
            
        }
        
            
            
        
        return answer;
    }
}