프로그래며스_[1차] 프렌즈4블록(JAVA)

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

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

프렌즈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개의 블록이 지워진다.

[풀이]

판의 세로 열마다 arraylist로 해당 문자열의 문자를 저장하여 해결하고 싶은데 character를 저장할 arraylist를 하나하나 선언하기에는 비효율적이라고 여겨 어떻게 해결할까 생각해보다 Arraylist 안에 Arraylist를 저장하여 해결하면 되겠다고 생각했다. 그래서 ArrayList에 char를 저장할 arraylist를 넣어주기 위해 ArrayList<ArrayList<Character>> b를 선언하여 사용하였다. 

위 입출력 예제 예제 1의 경우 초기 b에는 값이 다음과 같이 저장된다.

arraylist 안의 arraylist에는 각 열이 저장될 것이고, 저장되는 순서는 가장 밑에 존재하는 블록이 가장 처음 위치에 저장되게 된다. 오른쪽부터 세로로 읽어보면 입력된 판의 정보 순서대로임을 알 수 있다. 

이는 본인 밑에 있는 블록이 제거되면 해당 블록이 밑의 위치로 내려와야하기 때문에 다음과 같이 저장하였다.

 

더이상 제거되는 블록이 없을 때까지 반복문을 돌려 검사한다. 

 

1. 현재 위치의 블록을 기준으로 오른쪽(j+1), 아래(i+1), 오른쪽 아래 대각선(i+1, j+1)에 존재하는 블록을 비교한다. 

다음 블록들이 모두 같다면 제거 대상인 것이다. 그렇지만 해당 블록들을 바로 제거해서는 안된다. 겹쳐서 제거되는 블록이 존재할 수도 있기 때문이다. 따라서 제거 대상이 될 블록을 체크하기 위해 boolean[][] v를 이용할 것이다.

 

    1-1. 현재 위치의 블록이 제거 대상이고, v[i][j]가 false라면 해당 값을 true로 변경해주고 총 제거 블록 개수를 저장하는 변수 answer를 1 증가(answer++)시켜준다.

    1-2. 만약 현재 위치의 블록이 제거 대상이지만 v[i][j]가 true라면 이미 answer를 1 증가시켜줬을 것이므로 별다른 변화 없이 진행한다.

    1-3. 현재 위치의 블록이 제거 대상이 아니라면 별 다른 변화없이 다음 블록을 검사하면 된다.

 

위의 1번 과정에서 인접한 위치의 블록을 검사하기 전에 확인해야 할 값이 있다. 그것은 현재 위치의 블록이 '0' 인지 아닌지이다. 이는 밑에서 다시 설명하도록 하겠다.

 

2. 1번 과정이 모든 블록에 대해 완료되고 나면 이제 블록들을 제거해줄 차례이다. 제거는 가장 오른쪽 값부터 해줄 것이다. 0번째 index부터 검사하여 제거하고 나면 그 다음 index의 블록이 앞으로 자동으로 이동되게 될 것인데 그렇다면 boolean 배열의 index값과 일치되지 않는 일이 발생하게 될 것이다. 따라서 가장 위에 존재하는 블록부터 제거해줄 것이다. 제거해야할 블록인지 아닌지는 1번 과정에서의 v값으로 판단한다.

해당 위치의 v값이 true라면 제거 대상인 것이므로 해당 블록을 제거해주고, 판의 모양을 유지해주기 위해 가장 상위에 '0'을 넣어준다. 이 때문에 1번 과정에서 가장 먼저 확인해야 할 것이 해당 위치의 블록 값이 '0'인지 아닌지라는 것이다. '0'인 것은 해당 위치가 비어있다는 것을 의미하므로 인접 블록들을 검사할 필요가 없다.

 

3. 제거 대상인 블록을 모두 제거하고나서 t값과 answer값을 비교하는데, 이는 제거된 블록이 있는가 없는가를 확인하기 위해서이다.

    3-1. t값과 answer값이 같다면 answer값의 변화가 없었다는 것이고, 이번 차례의 반복문에서는 제거된 블록이 없고 더 이상 제거될 블록이 없다는 것을 의미한다. 따라서 해당 두 값의 크기가 같다면 반복문을 종료한다.

    3-2. t값과 answer값이 다르다면 제거된 블록이 있었으므로 다음 반복문 시작 시, t값에 현재 answer값을 넣어주고 1번 과정부터 다시 반복하면 된다.

 

 

[코드]

import java.util.*;
class Solution {
    public int solution(int m, int n, String[] board) {
        int answer = 0;
        ArrayList<ArrayList<Character>> b = new ArrayList<ArrayList<Character>>();
        
        for(int i=0;i<n;i++){
            ArrayList<Character> temp = new ArrayList<>();
            for(int j=m-1;j>=0;j--){
                temp.add(board[j].charAt(i));
            }
            b.add(temp);
        }
        
        int t = answer;
        
        while(true){
            t=answer;
            boolean[][] v = new boolean[n][m];
        
            for(int i=0;i<n-1;i++){
                for(int j=0;j<m-1;j++){
                    char c = b.get(i).get(j);
                    if(c=='0')
                        continue;

                    if(c==b.get(i).get(j+1)&&c==b.get(i+1).get(j)&&c==b.get(i+1).get(j+1)){
                        if(!v[i][j]){
                            v[i][j]=true;
                            answer++;
                        }
                        if(!v[i][j+1]){
                            v[i][j+1]=true;
                            answer++;
                        }
                        if(!v[i+1][j]){
                            v[i+1][j]=true;
                            answer++;
                        }
                        if(!v[i+1][j+1]){
                            v[i+1][j+1]=true;
                            answer++;
                        }
                    }
                }
            
            }
         
           
            for(int i=0;i<n;i++){
                for(int j=m-1;j>=0;j--){
                    if(v[i][j]){
                        b.get(i).remove(j);
                        b.get(i).add('0');
                       
                    }
                }
            }
         
            if(t==answer)
                break;
            
        }
        return answer;
    }
}