2018 KAKAO BLIND - 프렌즈4블록

1. 문제

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

2. 접근

 

배열의 모든 인접 요소를 확인해야 되는 완전 탐색 문제다.

하나의 요소를 기준으로 아래, 오른쪽, 오른쪽아래 대각선만 확인하는 방식으로 탐색을 진행했다.

배열의 크기가 M*N이므로 M-1,N-1까지만 반복문을 돌리면 됐다.

i)

만약, 조건을 만족해서 지울 수 있는 블록을 발견할 경우 바로 지우지 않고 위치만 기억해 두고 끝까지 탐색을 계속했다. 탐색하는 도중 지워버리면 다른 인접 요소에 영향을 받아 예외가 생길 수 있기 때문이다.

ii)

탐색이 끝나면 저장해둔 위치의 블록들을 모두 지우고 블록들을 아래로 끌어 내렸다.

방법은 세로 한 줄씩 아래 -> 위 방향으로 탐색하며 빈칸 위에 블록이 있다면 내렸다.

 

블록을 모두 검사해서 지울 블록이 없을 때까지 i와 ii를 반복한 후 결과를 리턴했다.

 

3. 코드

class Solution {
    public int solution(int m, int n, String[] board) {
        int answer = 0;

        char[][] block = new char[m][n];
        for(int i=0;i<m;i++){
            String str = board[i];
            for(int j=0;j<n;j++){
                block[i][j] = str.charAt(j);
            }
        }

        while(end(block, m, n)){ // 더 이상 지울 블록이 남아 있는가?
            ArrayList<Node> list = new ArrayList<>();
            for(int i=0;i<m-1;i++){
                for(int j=0;j<n-1;j++){
                    char ch = block[i][j];
                    if(isDelete(block, ch, i, j)){ // 지울 수 있다면
                        list.add(new Node(i,j)); // 미리 지우지 않고 인덱스만 저장해 놓는다
                    }
                }
            }
            makeDeleteBlock(block, list);
            startDelete(block,m,n);
        }

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(block[i][j]=='-'){
                    answer++;
                }
            }
        }


        return answer;
    }

    public boolean end(char[][] block,int m, int n){
        for(int i=0;i<m-1;i++){
            for(int j=0;j<n-1;j++){
                char ch = block[i][j];
                if(isDelete(block, ch, i, j)){ // 지울 수 있다면
                    return true;
                }
            }
        }
        return false;
    }

    public boolean isDelete(char[][] block, char ch, int i, int j){
        if(ch!= '-' && ch == block[i+1][j] && block[i+1][j] == block[i+1][j+1] 
        && block[i+1][j+1] == block[i][j+1]){
            return true;
        } else {
            return false;
        }
    }

    public void makeDeleteBlock(char[][] block, ArrayList<Node> list){
        for(int i=0;i<list.size();i++){
            Node n = list.get(i);
            int x = n.x;
            int y = n.y;
            block[x][y] = '-'; // 빈칸은 '-'로 표시
            block[x+1][y] = '-';
            block[x+1][y+1] = '-';
            block[x][y+1] = '-';
        }
        list.clear();
    }
    
    public void startDelete(char[][] block, int m, int n){
        for(int i=0;i<n;i++){ // 왼쪽 세로줄 부터 아래 -> 위 방향으로 탐색
            int idx = -1;
            for(int j=m-1;j>=0;j--){
                if(idx == -1 && block[j][i]=='-'){
                    idx = j;
                }
                if(idx!=-1 && block[j][i]!='-'){ // 블록 끌어내리기기                    
                    block[idx][i] = block[j][i];
                    block[j][i] = '-';
                    j = idx;
                    idx = -1;
                }
            }
        }
    }
}

class Node{
    int x;
    int y;
    Node(int x, int y){
        this.x = x;
        this.y = y;
    }
}

4. 결과

 

끝.