프로그래머스 lv2 프렌즈4블록

문제 링크

프렌즈4블록

풀이

• 문제 접근부터 굉장히 헷갈렸다. 이게 BFS인지, 완전탐색인지...헷갈렸기 때문
• 복잡한 문제일수록 간단하게 생각하면 쉽다...를 다른 사람이 풀어놓은 것을 보고 깨달았다.
• 전체 탐색을 하면서, 2x2 블록을 탐색하고 조건에 부합한다면 그 부분만 다른 배열에 표시해 둔 다음, 전체 탐색이 끝난 뒤에 해당되는 부분은 지우고, 배열을 아래로 땡겨오면 된다.
• 그 다음에는 지워지지 않은 부분에 대한 전체 탐색을 다시 시작하면 된다.

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    static boolean[][] v;   // 체크 배열

    public int solution(int m, int n, String[] board) {
        int answer = 0;
        char[][] copy = new char[m][n];
        for (int i = 0; i < m; i++) {
            copy[i] = board[i].toCharArray();
        }

        boolean flag = true; // 중복 탐색할 것이 남았는지에 대한 flag
        while (flag) {
            v = new boolean[m][n];
            flag = false;
            for (int i = 0; i < m - 1; i++) {
                for (int j = 0; j < n - 1; j++) {
                    if (copy[i][j] == '#') continue; // #은 빈칸을 의미
                    if (check(i, j, copy)) {    // 현재 칸에 인접한 3칸이 모두 같은 값인가? 에 대한 check
                        v[i][j] = true;
                        v[i][j + 1] = true;
                        v[i + 1][j] = true;
                        v[i + 1][j + 1] = true;
                        flag = true;
                    }
                }
            }
            answer += sortingArr(m, n, copy);
            v = new boolean[m][n];
        }
        return answer;
    }

    public static boolean check(int x, int y, char[][] board) {
        char ch = board[x][y];
        return ch == board[x][y + 1] && ch == board[x + 1][y] && ch == board[x + 1][y + 1];
    }
    
    public static int sortingArr(int m, int n, char[][] board) {
        int cnt = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (v[i][j])
                    board[i][j] = '.';
            }
        }

        // 큐를 통해서 2차원 배열 정렬
        for (int i = 0; i < n; i++) {
            Queue<Character> q = new LinkedList<>();
            for (int j = m - 1; j >= 0; j--) {
                if (board[j][i] == '.') {
                    cnt++;  // 지우는 블록 카운트
                } else {
                    q.add(board[j][i]);
                }
            }
            int idx = m - 1;
            // 삭제한 블록 위의 블록들 내리기
            while (!q.isEmpty()) {
                board[idx--][i] = q.poll();
            }
            // 빈칸 채우기
            for (int j = idx; j >= 0; j--) {
                board[j][i] = '#';
            }
        }

        return cnt;
    }
}