[프로그래머스 Level.2] [1차] 프렌즈4블록 (2018 KAKAO BLIND RECRUITMENT) (Java)

문제 링크

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

프로그래머스

 

 

 

 

코딩테스트 연습 > 2018 KAKAO BLIND RECRUITMENT > [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개의 블록이 지워진다.

 

 

 

 

 

나의 코드

import java.util.*;

class Solution {
    
    char[][] block;
    boolean[][] checked;
    public int solution(int m, int n, String[] board) {
        int answer = 0;
        
        block = new char[m][n];
        checked = new boolean[m][n];
        
        for(int i=0; i<m; i++) {
            block[i] = board[i].toCharArray();
        }
        
        while(true) {
            int dropBlockCnt = updateBlock(m, n);
            if(dropBlockCnt == 0) break;
            answer += dropBlockCnt;
        }
        
        return answer;
    }
    
    public int updateBlock(int m, int n) {
        int cnt = 0;
        Queue<Character> q = new LinkedList<>();
        
        // 4개 묶인 블록들은 true
        for(int i=0; i<m-1; i++) {
            for(int j=0; j<n-1; j++) {
                if(block[i][j] != 'X' && checkBlock(i, j)) {
                    checked[i][j] = true;
                    checked[i+1][j] = true;
                    checked[i][j+1] = true;
                    checked[i+1][j+1] = true;
                }
            }
        }
        
        // 제거 후 위치 조정
        for(int i=0; i<n; i++) {
            for(int j=m-1; j>=0; j--) {
                if(checked[j][i]) {
                    cnt++;
                    checked[j][i] = false;
                    continue;
                }
                q.offer(block[j][i]);
            }
            
            for(int j=m-1; j>=0; j--) {
                if(!q.isEmpty()) {
                    block[j][i] = q.poll();
                } else {
                    block[j][i] = 'X';
                }
            }
        }
        
        return cnt;
    }
    
    // 4개 블록 같은지 확인
    public boolean checkBlock(int i, int j) {
        char nowBlock = block[i][j];
        if(block[i+1][j] == nowBlock && block[i][j+1] == nowBlock && block[i+1][j+1] == nowBlock)
            return true;
        
        return false;
    }
    
}

 

풀이

1. 문제를 보면 board[board.length-1]이 제일 아래 깔리고 board[0]이 제일 위에 쌓이고 블록의 높이는 m = board.length, 폭은 n = board[0].length() 라는 것을 알 수 있다.
2. 블록을 만들기 위해 char 타입의 2차원 배열 block을 생성하고 String 타입의 board 배열을 for문을 돌면서 toCharArray()를 통해 block을 채운다. 
3. 이제 이 block 배열을 가지고 블록을 확인하여 블록을 제거 할 수 있는 조건에 만족하여 블록을 제거한다면 제거한 빈 공간을 고려하여 블록을 위치시키고 제거한 블록의 개수를 카운팅하는 것을 지워지는 블록이 없을 때까지 반복하면 된다.
4. 2x2 형태가 같은 블록이어서 제거 대상인 블록을 구분하기 위해 block과 크기가 같은 boolean 타입의 2차원 배열을 생성하였고 블록을 제거하고 블록을 다시 위치시키는 것을 updateBlock 메소드를 만들어서 구현하였다.
   이중 for문을 통해 block[i][j]를 기준으로 블록 block[i][j], block[i][j+1], block[i+1][j], block[i+1][j+1]이 같다면 2x2 형태로 같은 블록이므로 제거 대상으로 판단하고 해당 위치의 checked를 true로 변경한다. i,j를 기준으로 i+1, j+1을 확인하므로 이중 for문의 조건식은 i<m-1, j<n-1으로 한다.
5. 제거 대상을 판별하였으면 이 블록들을 제거하고 블록의 위치를 다시 조정해주면 되는데 이 때도 다시 이중 for문을 통해 구현하였다. 블록의 위치를 재조정 할 때는 큐를 이용하도록 했다.
   첫 번째 열부터 차례로 블록을 제거하고 블록의 위치를 재조정 하기 위해 첫 번째 for문이 열을 두 번째 for문이 행을 탐색하도록 한다. 그리고 밑에서부터 블록을 확인하기 위해 행을 탐색하는 두 번째 for문은 m-1부터 시작하여 0 인덱스까지 탐색하도록 한다.
   블록의 탐색 순서 : 맨 왼쪽 아래 ~ 맨 왼쪽 위 -> 두 번째 왼쪽 아래 ~ 두 번째 왼쪽 위 -> ...... -> 맨 오른쪽 아래 -> 맨 오른쪽 위
6. 이중 for문을 돌면서 제거 대상으로 판별했던 checked가 true이면 제거 블록을 카운팅하고  checked를 false로 바꾼다. 제거 대상이 아니라면 블록이 남아있어야 하므로 큐에 해당 블록을 담는다. 이렇게 한 열을 다 돌았으면 다시 for문을 만들어 큐에 블록이 있으면 아래에서부터 다시 쌓고 블록이 없다면 나머지는 빈 공간으로 구분하기 위해 'X'로 채우도록 한다. 이렇게 마지막 열까지 다 돌면 한 턴의 모든 제거 대상 블록을 제거하고 블록을 재조정 시키게 되는 것이다.
7. 이 과정을 반복하다 제거 할 블록이 더 이상 없으면 반복문을 종료하고 블록을 제거하면서 카운팅 했던 제거한 블록의 수를 리턴한다.