[프로그래머스] Lv.2 : [1차] 프렌즈4블록 - 자바[Java]

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

프로그래머스

풀이

로직은 다음과 같다.

 

1. 2x2 로 배치된 블록 찾기

- char[][] map, boolean[][] check

- 지우는 블록의 위치에 check[i][j] = true

 

2. 블록 지우기(중복 고려) + 지우는 블록의 개수를 세면서 해당 위치의 map을 'x'으로 변경

주의할 점

check[i][j] = false로 복구해야 한다.

 

3. 블록이 지워진 후 위에 있는 블록을 아래로 옮기기

- 열마다 아래부터 탐색하면서 x를 만나면 prev로 그 위치를 저장하고, 바로 위부터 올라가며 탐색하다가 블록을 만나면 해당 위치는 x로 바꾼 다음 prev 위치에 해당 블록으로 변경한다.

- 블록을 모두 아래로 옮긴 다음, 블록 위쪽의 공간을 o로 변경한다.

주의할 점

블록을 지운 위치는 x, 블록 위쪽 공간은 o로 구분한다.

 

4. 1~3을 지우는 블록이 없을 때까지 반복

    static char[][] map;
    static boolean[][] check;
    
    public int solution(int m, int n, String[] board) {
        map = new char[m][n];
        check = new boolean[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                map[i][j] = board[i].charAt(j);
            }
        }
        
        int answer = 0;
        while (true) {
            findBlock(); // 2x2 블록 찾기
            
            int cnt = eraseBlock(); // 블록을 지우는 동시에 개수 세기
            if (cnt == 0) {
                break;
            }
            answer += cnt;
            
            moveDown(); // 블록을 아래로 이동
        }
        return answer;
    }

 

코드

class Solution {
    static char[][] map;
    static boolean[][] check;
    
    public int solution(int m, int n, String[] board) {
        map = new char[m][n];
        check = new boolean[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                map[i][j] = board[i].charAt(j);
            }
        }
        
        int answer = 0;
        while (true) {
            findBlock(); // 2x2 블록 찾기
            
            int cnt = eraseBlock(); // 블록을 지우는 동시에 개수 세기
            if (cnt == 0) {
                break;
            }
            answer += cnt;
            
            moveDown(); // 블록을 아래로 이동
        }
        return answer;
    }
    
    static void findBlock() {
        for (int i = 0; i < map.length - 1; i++) {
            for (int j = 0; j < map[0].length - 1; j++) {
                char ch = map[i][j];
                if (ch == 'o') continue;
                
                if (checkBlock(i, j, ch)) {
                    check[i][j] = true;
                    check[i+1][j] = true;
                    check[i][j+1] = true;
                    check[i+1][j+1] = true;
                }
            }
        }
    }
    
    static boolean checkBlock(int r, int c, char ch) {
        for (int i = r; i < r + 2; i++) {
            for (int j = c; j < c + 2; j++) {
                if (map[i][j] != ch) {
                    return false;
                }
            }
        }
        
        return true;
    }
    
    static int eraseBlock() {
        int cnt = 0;
        
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                if (check[i][j]) {
                    map[i][j] = 'x';
                    cnt++;
                    
                    check[i][j] = false; // check 배열 false로 초기화
                }
            }
        }
        
        return cnt;
    }
    
    static void moveDown() {
        for (int j = 0; j < map[0].length; j++) {
            int i = map.length - 1;
            while (i >= 0) {
                while (i >= 0 && map[i][j] != 'x') i--;
                if (i < 0) break;
                
                int prev = i;
            
                while (i >= 0 && map[i][j] == 'x') i--;
                
                // 맨 위까지 도달하거나 빈 공간을 만나면 break
                if (i < 0 || map[i][j] == 'o') break;
            
                map[prev][j] = map[i][j];
                map[i][j] = 'x';
                i = prev;
            }
            
            // 블록 위쪽 공간을 빈 공간(O)으로 변경
            for (i = 0; i < map.length; i++) {
                if (map[i][j] != 'x' && map[i][j] != 'o') break;
                map[i][j] = 'o';
            }
        }
    }
}