[프로그래머스] 카카오_프렌즈4블록 (자바 풀이)

문제

https://programmers.co.kr/learn/courses/30/lessons/17679?language=java 

코딩테스트 연습 - [1차] 프렌즈4블록

풀이

이 문제는 기능별로 함수를 적절히 나누어 풀었다.

 

1. 2*2 블록이 같은지 체크하는 함수

2. 블록을 제거하는 함수

 

2*2 블록이 같은지 체크하는 것은 간단하다. 그냥 현재 블록을 기준으로 오른쪽, 아래, 오른쪽 아래가 같은지 체크하면 된다. 이때 조심할 것은 배열의 범위를 벗어나지 않도록 해야 한다. 만약 2*2 블록이 같다면 이를 기록할 boolean[][] 배열에 따로 표시를 한다. 직접적으로 board 배열을 바꾸지 않는 이유는 모든 블록을 조사한 후에 일괄적으로 처리를 해야하기 때문이다. 

 

블록을 제거하는 것은 조금 신경을 써야 한다. 나는 큐를 이용해 세로로 블록을 제거하는 방법을 사용했다. 맨 아래에서부터 큐에 집어넣고, 제거해야 하는 블록이라면 개수만 세고 큐에 넣지 않는다. 이후 큐에 있는 원소들을 빼내서 아래부터 차곡차곡 블록을 쌓아준다. 빈 블록은 '#'으로 표시해준다.

 

이후 위 과정을 반복해서 2*2 블록이 없을 때 까지 반복해주면 된다.

 

코드

import java.util.*;
 
class Solution {
    static boolean v[][];   // 체크 배열
    
    public int solution(int m, int n, String[] board) {
        int answer = 0;
        // String 배열은 변경이 어려움. char 배열로 복사해서 사용
        char copy[][] = new char[m][n]; 
        for(int i=0; i<m ; i++){
            copy[i] = board[i].toCharArray();
        }
        
        boolean flag = true;
        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)){    // 2*2 체크
                        v[i][j] = true;
                        v[i][j+1] = true;
                        v[i+1][j] = true;
                        v[i+1][j+1] = true;
                        flag = true;
                    }
                }
            }
            answer += erase(m,n,copy);
            v = new boolean[m][n];
        }
        return answer;
    }
    
    /* 2*2가 같은지 체크 */
    public static boolean check(int x, int y, char[][] board){
        char ch = board[x][y];
        if(ch == board[x][y+1] && ch== board[x+1][y] && ch == board[x+1][y+1]){
            return true;
        }
        return false;
    }
    
    /* 같은 블록 제거 */
    public static int erase(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] = '.';
            }
        }
        
        /* 큐를 이용해 세로로 제거 작업 진행 */
        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;
    } 
}

결과