[알고리즘] 1차 프렌즈4블록

[1차] 프렌즈4블록

 

[문제 설명]

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 프렌즈4블록.
같은모양의카카오프렌즈블록이2×2형태로4개가붙어있을경우사라지면서점수를얻는게임이다.

만약판이위와같이주어질경우,라이언이2×2로배치된7개블록과콘이2×2로배치된4개블록이지워진다.같은블록은여러2×2에포함될수있으며,지워지는조건에만족하는2×2모양이여러개있다면한꺼번에지워진다.

블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.

만약빈공간을채운후에다시2×2형태로같은모양의블록이모이면다시지워지고떨어지고를반복하게된다.

위초기배치를문자로표시하면아래와같다.

TTTANT
RRFACC
RRRFCC
TRRRAA
TTMMMF
TMMTTJ

각문자는라이언(R),무지(M),어피치(A),프로도(F),네오(N),튜브(T),제이지(J),콘(C)을의미한다

입력으로블록의첫배치가주어졌을때,지워지는블록은모두몇개인지판단하는프로그램을제작하라.

 

[입력 형식]

- 입력으로판의높이m,폭n과판의배치정보board가들어온다.
- 2 ≦ n, m ≦ 30
- board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.

 

[출력 형식]

- 입력으로주어진판정보를가지고몇개의블록이지워질지출력하라.

 

[입출력 예]

m	n	board	answer
4	5	["CCBDE","AAADE","AAABF","CCBBF"]	14
6	6	["TTTANT","RRFACC","RRRFCC","TRRRAA","TTMMMF","TMMTTJ"]	15

 

[예제에 대한 설명]

- 입출력예제1의경우,첫번째에는A블록6개가지워지고,두번째에는B블록4개와C블록4개가지워져,모두14개의블록이지워진다.
- 입출력 예제 2는 본문 설명에 있는 그림을 옮긴 것이다. 11개와 4개의 블록이 차례로 지워지며, 모두 15개의 블록이 지워진다.

 

 

[적용 소스]

import java.util.ArrayList;
class Solution {
        public int solution(int m, int n, String[] board) {
            String totBd = ""; // 전체 board 문자열
            for(String a: board) totBd+=a;
 
            char[] chrBd = totBd.toCharArray();
            int answer = chrBd.length;
 
            while(true){
                ArrayList<Integer> rmvIdx = new ArrayList<>();
                for(int i=0; i<chrBd.length-(n+1); i++){
                    if(chkBlock2x2(chrBd, i, n)) rmvIdx.add(i);
                }
 
                if(rmvIdx.size()>0) chrBd=rmvBlock2x2(chrBd, rmvIdx, m, n);
                else break;
            }
            
            String chrToStrBd=String.valueOf(chrBd);
            chrToStrBd=chrToStrBd.trim().replaceAll(" ", "");
            return answer-chrToStrBd.length();
        }
 
        // 블록 체크
        private boolean chkBlock2x2(char[] data, int i, int n){
            if(data[i]==' '||data[i]!=data[i+1]||i%n==n-1)
                return false;
 
            String comp=String.valueOf(data[i]+data[i+1]);
            String str=String.valueOf(data[i+n]+data[(i+1)+n]);
            if(!comp.equals(str)) return false;
 
            return true;
        }
 
        // 블록 제거
        private char[] rmvBlock2x2(char[] chrBd, ArrayList<Integer> rmvIdx, int m, int n){
            for(int i:rmvIdx){
                chrBd[i]=' ';
                chrBd[i+1]=' ';
                chrBd[i+n]=' ';
                chrBd[(i+1)+n]=' ';
            }
            return replBlock2x2(chrBd, m, n);
        }
 
        // 블록 재배열
        private char[] replBlock2x2(char[] chrBd, int m, int n){
            for(int i=m-1; i>0; i--) {
                for (int j=i*n; j<i*n+n; j++) {
                    for(int k=n; k<=j; k=k+n){
                        if(chrBd[j-k]==' ')continue;
                        if (chrBd[j]==' '){
                            chrBd[j]=chrBd[j-k];
                            chrBd[j-k]=' ';
                        }
                        break;
                    }
                }
            }
            return chrBd;
        }
    }

 

 

[25~35] : 2x2블록 조건이 만족하는지 체크

[37~46] : 2x2블록 조건 만족 시 빈 값으로 제거 표시

[48~63] : 제거된 블록에 의한 재배열

 

 

 

 

 

 

 

 

* 해당 글은 프로그래머스 페이지에서 제공받은 문제로 작성하였습니다. 출처:https://programmers.co.kr/

프로그래머스