프로그래머스 Lv.2) 프렌즈4블록

2018 KAKAO BLIND RECRUITMENT [1차]

프렌즈4블록

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

풀이

이 문제는 큰 어려움 없이 푼 것 같다. 전체 board를 돌면서 4개가 모여있는 구역을 int 배열을 통해 표시해주고, 전체 탐색이 끝날 때 마다 표시된 구역을 지우면서 카운트를 세주었다. 이 때, 지워진 블록 위에 있는 블록들을 아래로 하나씩 내리면서 블록을 당겨주었다. while문을 통해 삭제가 진행되지 않을 때 까지 진행해주었다.

 

로직

1. 전체 board를 돌면서 4개가 모여있는 구역을 체크해둔다.

2. 전체 탐색이 끝난 뒤 체크된 구역을 지운다.

 2-1. 구역을 지우면서 카운트를 세준다.

 2-2. 지워진 구역 위의 블록들을 아래로 내려준다.

3. 블록 삭제가 진행되지 않을 때 까지 반복한다.

 

코드

class Solution {
    final static int[] dx = {1, 1, 0}, dy = {0,1,1};
    static int answer;
    public int solution(int m, int n, String[] board) {
        answer = 0;
        char[][] chBoard = new char[m][n];
        for(int y=0; y<m; y++) {
            chBoard[y] = board[y].toCharArray();
        }
        delete(m,n,chBoard);
        return answer;
    }
    
    private char[][] delete(int m, int n, char[][] board) {
        int prev = answer-1;
        while(prev != answer) {
            prev = answer;
            int[][] delete = new int[m][n];
            for(int y=0; y<m-1; y++) {
                for(int x=0; x<n-1; x++) {
                    char origin = board[y][x];
                    if(origin != ' ') {
                        if(canRemove(origin, board, x, y)) {
                            delete = setDelete(delete, x, y);
                        } 
                    }
                }
            }
            board = setBoard(delete, board, m,n);
        }
        return board;
    }
    private boolean canRemove(char origin, char[][] board, int x, int y) {
        for(int i=0; i<3; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            char target = board[ny][nx];
            if(origin != target) {
                return false;
            }
        }
        return true;
    }
    private int[][] setDelete(int[][] delete, int x, int y) {
        delete[y][x] =1;
        for(int i=0; i<3; i++) {
            delete[y+dy[i]][x+dx[i]] =1;
        }
        return delete;
    }
    private char[][] setBoard(int[][] delete, char[][] board, int m, int n) {
        for(int y=0; y<m; y++) {
            for(int x=0; x<n; x++) {
                if(delete[y][x] ==1) {
                    answer++;
                    board[y][x] = ' ';
                    for(int ny =y; ny>=0; ny--) {
                        if(ny-1 >=0) {
                            board[ny][x] = board[ny-1][x];
                            board[ny-1][x] = ' ';
                        }    
                    }
                }
            }
        }
        return board;
    }
}