[PGM_17679] 프렌즈 4블록

문제링크

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

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

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 구현

1. 문제 이해

프렌즈 4블록 게임은 2x2로 이루어진 블록이 제거되는 게임이다.

출처-프로그래머스

위 그림을 보면 라이언과 콘이 2x2로 겹쳐있는 것을 볼 수 있다. 이 경우 해당하는 블록을 제거해주며 된다. 이 때 라이언처럼 겹치게 2x2를 만족하면 겹치는 부분을 포함하여 제거해줄 수 있다는 것을 주의해서 해결해야한다. 그리고 제거를 해주면 위에 있는 블럭들을 제거된 블러까지 내려주어 다시 2x2를 찾아 제거해준다. 이 때 제거되는 블럭의 개수를 구해주는 문제이다.

 

2. 접근방법

문제를 해결하기 위해서 모든 블록의 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래에 대하여 각각 확인해주었다. 만약 조건을 만족한다면 해당  2x2블럭은 삭제되어야 할 것이다. 문제를 해결하기 위해서 순서가 굉장히 중요하다.

 

1. 삭제될 블럭을 체크한다.

2. 체크된 블럭을 제거한다.

3. 삭제된 위치의 위에 있는 블럭들을 내려준다.

4. 더 이상 삭제가 되지 않을 때 까지 반복한다.

 

이 방법으로 코드를 구현하여 문제를 해결하였다.

구현코드

package pgm_17679;

public class Solution {
    public int solution(int m, int n, String[] board) {
        char[][] c_board = new char[m][n];
        for(int i = 0; i < m; i ++){
            for(int j = 0;  j < n; j++){
                c_board[i][j] = board[i].charAt(j);
            }
        }
        boolean change;
        do {
            boolean[][] checked = new boolean[m][n];
            change = breakBlock(m,n,c_board,checked);
            removeBlock(m,n,c_board,checked);
            moveDownBlock(m,n,c_board);
        }while (change);

        moveDownBlock(m,n,c_board);
        return removedBlockCount(m,n,c_board);
    }

    public int removedBlockCount(int m, int n, char[][] board){
        int count = 0;
        for(int i =0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(board[i][j] == '-')
                    count++;
            }
        }
        return count;
    }

    public void moveDownBlock(int m, int n, char[][] board){
        for(int i = m-1; i >= 0; i--){
            for(int j = n-1; j >= 0; j--){
                if(board[i][j] == '-'){
                    filledBlock(i,j,m,n,board);
                }
            }
        }
    }

    private void filledBlock(int x, int y, int m, int n, char[][] board){
        boolean valid = false;
        for(int k = 0; k+x > 0; k--){
            if(!valid && board[k+x-1][y] != '-')
                valid = true;
            char temp = board[k+x][y];
            board[k+x][y] = board[k+x-1][y];
            board[k+x-1][y] = temp;
        }

        if(valid && board[x][y] == '-')
            filledBlock(x,y,m,n,board);
    }

    public void removeBlock(int m, int n, char[][] board, boolean[][] checked){
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(checked[i][j])
                    board[i][j] = '-';
            }
        }
    }

    public boolean breakBlock(int m, int n, char[][] board, boolean[][] checked){
        int[][] dx = {{-1,-1,0},{-1,-1,0},{0,1,1},{0,1,1}};
        int[][] dy = {{0,-1,-1},{0,1,1},{-1,-1,0},{1,1,0}};
        boolean removed = false;

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j ++){
                char check = board[i][j];
                if(check == '-')
                    continue;
                for(int k = 0; k < 4; k++){
                    boolean remove = false;
                    int[] disX = dx[k];
                    int[] disY = dy[k];

                    for(int ptr = 0; ptr < 3; ptr ++) {
                        if (validBoundary(m, n, i + disX[ptr], j + disY[ptr])
                            || check != board[i+disX[ptr]][j + disY[ptr]])
                            break;
                        if(ptr == 2) {
                            remove = true;
                            removed = true;
                        }
                    }

                    if(remove){
                        checked[i][j] = true;
                        for(int ptr = 0; ptr < 3; ptr ++) {
                            checked[i+disX[ptr]][j + disY[ptr]] = true;
                        }
                    }
                }
            }
        }
        return removed;
    }

    private boolean validBoundary(int m, int n, int x, int y){
        return x < 0 || y < 0 || x >= m || y >= n;
    }
}

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)