[알고리즘] 2018 카카오 블라인드 - 프렌즈4블록

1. 문제

2. 문제 풀이

블록을 아래로 내리는 부분이 좀 까다롭고 나머지는 문제에 주어진대로 풀면 되는 문제였다.

 

1. 주어진 1차원 배열을 2차원 배열로 옮긴다.

2. 2*2영역이 같을 경우 해당 영역을 check 2차원 배열에 true로 표시한다.

3. check 2차원 배열에 true로 표시된 공간을 블록이 터졌다는 의미로 "*"로 바꾼다.

4. 블록을 터트린 후 위에 있던 블록들을 아래로 내린다.

 

블록을 내리는 downBlock() 메서드의 경우 하나라도 내려간 블록이 있으면 해당 열의 블록을 내리는 작업을 다시 반복하였다. 내려가는 블록이 없을 경우 다음 열을 검사한다.

import java.util.*;

class Solution {

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

        //1. 2차원 배열에 담음
        String[][] newBoard = new String[m][n];
        boolean[][] check = new boolean[m][n];

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                newBoard[i][j] = String.valueOf(board[i].charAt(j));
            }
        }

        printBoard(newBoard, m, n);

        //2.  2*2 배열 지우고 밑으로 내리는 과정 반복
        while (true){
            check = new boolean[m][n];
            int count = removeBlock(m, n, newBoard, check);
            answer += count;

            System.out.println("2*2 블록 제거 후");
            printBoard(newBoard, m, n);

            if(count == 0)
                break;

            downBlock(newBoard, m,n);
            System.out.println("블록 내린 후");
            printBoard(newBoard, m, n);
        }

        System.out.println(answer);
        return answer;
    }

    //블럭을 내려주는 함수
    public static void downBlock(String[][] newBoard, int m,int n) {
        int idx = 0;

        for(int i=m-1;i>=1;i--) {
            for(int j=0;j<n;j++) {

                idx = i;
                int count = 0;

                while(true) {
                    if(idx < 1 && count == 0)   //내려간 블록이 없으면 while문 탈출
                        break;
                    else if(idx < 1 && count != 0){ //블록중 하나라도 내려간게 있으면 다시 반복
                        idx = i;
                        count = 0;
                    }
                    else if(newBoard[i][j].equals("*") && !newBoard[idx-1][j].equals("*")) {
                        //바꾼다
                        String tmp = newBoard[idx][j];
                        newBoard[idx][j]=newBoard[idx-1][j];
                        newBoard[idx-1][j]=tmp;
                        count++;
                    } else
                        idx--;
                }
            }
        }
    }

    public static void printBoard(String[][] newBoard, int m, int n){
        for(String[] e:newBoard) {
            System.out.println(Arrays.toString(e));
        }
        System.out.println();
    }

    public static int removeBlock(int m, int n, String[][] newBoard, boolean[][] check){

        int count = 0;

        // 2*2 블록인곳 check true
        for(int i=0;i<m-1;i++){
            for(int j=0;j<n-1;j++){
                String s = newBoard[i][j];
                if((!s.equals("*")) && (s.equals(newBoard[i][j+1]) && s.equals(newBoard[i+1][j]) && s.equals(newBoard[i+1][j+1]))) {
                    check[i][j]=true;
                    check[i][j+1]=true;
                    check[i+1][j]=true;
                    check[i+1][j+1]=true;
                }
            }
        }

        //newBoard에서 true인 곳 제거
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(check[i][j]==true) {
                    newBoard[i][j]="*";
                    count += 1;
                }
            }
        }

        return count;
    }


    //문제풀이용 예시
    public static void main(String[] args) {
        String [] board = {"CCBDE", "AAADE", "AAABF", "CCBBF"};
        int m=4;
        int n=5;
        solution(m,n,board);
    }
}