[구현] 프로그래머스 프렌즈4블록 (실패 분석- 시간부족)

접근

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

구현 문제로 완전 탐색으로 풀었습니다.
배열의 크기가 최대 30x30입니다.
이 문제는 조건을 만족하도록 구현하면 됩니다.

저는 2가지 메서드를 만들어 구현했습니다
1. 2x2 블록이 만들어지는지 확인하고 만들 수 있다면 그 곳에 표시

 static boolean checkBlock(int row, int col){
        char target = newBoard[row][col];
        //1. 블록이 존재하지 않는 곳이면 false
        if(target=='.') return false;
        //2. 2x2 블록이 완성되는지 확인하기 위해 주위 2x2판 검사
        for(int i=0;i<3;i++){
            //3. 하나라도 다르면 false
            if(target!=newBoard[row+x[i]][col+y[i]]){
                return false;
            }
        }
        
        //3. 2x2 블록을 만들 수 있는 곳임을 표시
        visited[row][col]=true;
        for(int i=0;i<3;i++){
            visited[row+x[i]][col+y[i]]=true;
        }
        
        return true;
    }

2. 2x2 블록이 사라지면 새로운 블록판을 만드는 메서드

 static void makeBoard(int m, int n){
        //남아있는 블록의 수를 저장합니다.
        NeraseBlock=0;
        //세로의 Queue
        for(int i=0;i<n;i++){
            Queue<Character> q = new LinkedList<>();
           for(int j=0;j<m;j++){
               //사라지지 않은 블록을 Queue에 넣습니다.
               if(!visited[j][i] && newBoard[j][i]!='.') q.add(newBoard[j][i]);
           }
            
            int size = q.size();
            NeraseBlock+=size;
            //여기서부터는 Queue에 남아있는 블록들이 보드판 어디에 들어가야 하는지
            //생각해야합니다.
            //사라진 갯수만틈 보드판 위를 채웁니다.
            for(int j=0;j<m-size;j++){
                newBoard[j][i]='.';
            }
            //Queue에 꺼내지는 것들은 보드판에 쌓습니다.
            for(int j=m-size;j<m;j++){
                newBoard[j][i]=q.poll();
            }
                        
        }

여기서 Queue는 블록판의 세로를 기준으로 남아있는 블록을 쌓기 위해 이용했습니다.

풀이

import java.util.*;

class Solution {
    
    // 검사하는 판
    static int[] x ={0,1,1};//행
    static int[] y={1,0,1};//열
    
    static boolean[][] visited;
    static char[][] newBoard ;
    static int NeraseBlock;//Not erase block

    public int solution(int m, int n, String[] board) {
        int answer = 0;
        
        visited=new boolean[m][n];
        newBoard = new char[m][n];
        
        for(int i=0;i<m;i++){
            newBoard[i]= board[i].toCharArray();
        }
        
        while(true){
        boolean tag = false;
        for(int i=0;i<m-1;i++){
            for(int j=0;j<n-1;j++){
                if(checkBlock(i,j)){
                    answer++;  
                    tag=true;
                }  
            }//j
          }//i
        makeBoard(m,n);
        visited=new boolean[m][n];
            
        if(!tag) break;                   
        }
       
        
        answer = m*n-NeraseBlock;
        
        return answer;
        
    }
    static boolean checkBlock(int row, int col){
        char target = newBoard[row][col];
        //1. 블록이 존재하지 않는 곳이면 false
        if(target=='.') return false;
        //2. 2x2 블록이 완성되는지 확인하기 위해 주위 2x2판 검사
        for(int i=0;i<3;i++){
            //3. 하나라도 다르면 false
            if(target!=newBoard[row+x[i]][col+y[i]]){
                return false;
            }
        }
        
        //3. 2x2 블록을 만들 수 있는 곳임을 표시
        visited[row][col]=true;
        for(int i=0;i<3;i++){
            visited[row+x[i]][col+y[i]]=true;
        }
        
        return true;
    }
    
   static void makeBoard(int m, int n){
        //남아있는 블록의 수를 저장합니다.
        NeraseBlock=0;
        //세로의 Queue
        for(int i=0;i<n;i++){
            Queue<Character> q = new LinkedList<>();
           for(int j=0;j<m;j++){
               //사라지지 않은 블록을 Queue에 넣습니다.
               if(!visited[j][i] && newBoard[j][i]!='.') q.add(newBoard[j][i]);
           }
            
            int size = q.size();
            NeraseBlock+=size;
            //여기서부터는 Queue에 남아있는 블록들이 보드판 어디에 들어가야 하는지
            //생각해야합니다.
            //사라진 갯수만틈 보드판 위를 채웁니다.
            for(int j=0;j<m-size;j++){
                newBoard[j][i]='.';
            }
            //Queue에 꺼내지는 것들은 보드판에 쌓습니다.
            for(int j=m-size;j<m;j++){
                newBoard[j][i]=q.poll();
            }
                        
        }
        
    }
      
}