프렌즈4블록

 

2017년 KAKAO BLIND RECURITMENT [1차]에 출제된 문제입니다.

 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17679

코딩테스트 연습 - [1차] 프렌즈4블록 | 프로그래머스

문제

카카오프렌즈 블록이 주어졌을 때 2*2 형태로 같은 모양이면 사라지는 게임이다.

 

사라져서 빈공간은 위에 있던 블록들이 내려오게 된다.

 

1. 아래와 같이 주어지면 2*2 블록은 사라진다. 3행 2열과 같이 중복되는 경우에는 한 번에 사라지게 된다.

 

 

2. 사라져서 빈공간이 생기면 위에 있던 블록으로 채워진다.

 

 

3. 빈 공간을 채웠을 때 2x2형태로 같은 모양이 존재하면 다시 지워지고 떨어지고를 반복하게 된다.

 

 

4. 2x2형태가 존재하지 않을 때까지 반복한다.

 

 

위 초기 배치를 문자로 표시하면 아래와 같다.

 

TTTANT RRFACC RRRFCC TRRRAA TTMMMF TMMTTJ

 

* 입력 형식
: 입력으로 판의 높이 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. 데이터를 보관하기위해 2차원 배열을 사용하였다.

 

* char[][] workingBoard : 실제 그림데이터를 보관하기 위함.

* boolean [][] resultBox : 터뜨려야 할 대상들을 체크하기 위함.

 

2. 모든 블록을 점검하여 2x2범위의 그림이 동일한지 확인한다.

 

ex) 우측, 아래, 우측 대각선의 그림이 동일한지 확인한다.

0,0	0,1
1,0	1,1

 

* 메서드 : boolean trueCheck(int mM, int nN)

 

3. 2에서 메서드의 리턴 값이 true인 경우에는 해당 위치를 모두 true로 변경해준 후 개수를 카운트해준다.

 

4. 3에서 카운트된 대상이 존재하면 대상 그림들을 터뜨린 후 빈 공간을 채워준다. ( 그림의 이니셜을!로 변경해 준다 )

 

* 열을 기준으로 바닥부터 검사를 한다.

* Queue를 사용하여 빈 공간의 index번호를 add()한다.

* 그림의 이니셜부분은 빈공간의 index가 Queue에 존재하면 순서대로 채워준다.

* 내려간 공간은 다시 비워준다 ( ! 와 true로 바꿔준다 )

* 비워진 공간을 다시 Queue에 add()한다. ( 위에 처리 대상이 더 존재하는 경우에 빈 공간에 채워주기 위해서 )

 

* 메서드 : void build(String [] board)에서else부분에 해당

 

5. 1~4를 반복하다가 3에서 카운트된 대상이 존재하지 않으면 처리된 개수를 출력 후 종료한다.

코드

package ProgrammersSummer;
 
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class BlockOf4 {
 
    static int[] pointM = { 1, 1, 0, 0 };
    static int[] pointN = { 0, 1, 0, 1 };
 
    // 최종터뜨릴 대상 확인
    static boolean[][] resultBox;
 
    // 2차원배열에 담기위함
    static char[][] workingBoard;
 
    static int m, n = 0;
 
    static int r = 0;
 
    public static void main(String[] args) {
 
        Scanner scan = new Scanner(System.in);
 
        m = scan.nextInt(); // 높이
        n = scan.nextInt(); // 가로
        scan.nextLine();
        String input = scan.nextLine();
 
        String[] board = input.split(",");
 
        workingBoard = new char[m][n];
        resultBox = new boolean[m][n];
 
        int cnt = 0;
 
        build(board);
 
        cnt = solution(m, n, board);
 
        System.out.println(cnt);
 
    }// main
 
    public static int solution(int mM, int nN, String[] board) {
 
        int answer = 0;
 
        boolean endPoint = true;
 
        // 전체순회한다.
        // 현재 노드를 기준으로 2*2대상을 보기때문에 -1까지만 보면 됨.
        while (true) {
            for (int i = 0; i < m - 1; i++) {
                for (int j = 0; j < n - 1; j++) {
                    boolean result = false;
                    result = trueCheck(i, j);
                    if (result) {
 
                        // 성립하면 true로 변경해줌
                        for (int k = 0; k < 4; k++) {
 
                            int nextM = i + pointM[k];
                            int nextN = j + pointN[k];
 
                            if (!resultBox[nextM][nextN]) {
 
                                endPoint = false;
                                answer++;
                                resultBox[nextM][nextN] = true;
 
                            }
                        }
                    }
                    // if ( i==m-2 && j==n-2 ) endPoint = true;
                }
            }
            if (endPoint)
                break;
            endPoint = true;
            build(null);
        }
 
        return answer;
 
    }// solution
 
    private static void build(String[] board) {
 
        if (board != null) {
            System.out.println("[ 최초 수행되는 빌드작업 .. ]  "+"\n");
            // String배열을 2차원 char배열에 담아주는 작업.
            for (int i = 0; i < m; i++) {
                char[] tempBoard = board[i].toCharArray();
                for (int j = 0; j < n; j++) {
                    workingBoard[i][j] = tempBoard[j];
                }
            }
            
            // 출력확인
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    System.out.print(workingBoard[i][j] + "\t");
                }
                System.out.println();
            }
 
        } else {
            System.out.println();
            // 아래로 내려주는작업.
            for (int i = 0; i < n; i++) {
                
                Queue<Integer> q = new LinkedList<Integer>();
                
                for (int j = m-1; j >= 0; j--) {
                    
                    if( resultBox[j][i] ) {
                        workingBoard[j][i] = '!'; // 처리된거 터뜨려주기 !! 
                        q.add(j);// i 의 인덱스를 Queue에 보관하기 !! 
                    }else { 
                        
                        if ( !q.isEmpty() ) {
                            int pollInt = q.poll();
                            char tempC = workingBoard[j][i];
                            workingBoard[j][i] = '!' ;
                            resultBox[j][i] = true;
                            workingBoard[pollInt][i] = tempC;
                            resultBox[pollInt][i] = false;
                            q.add(j);
                        }
                    }
                }
            }
            
            System.out.println( "[ " + r++ + "번째 Build 결과 .. ]"+"\n");
            //출력확인
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    System.out.print(workingBoard[i][j] + "\t");
                }
                System.out.println();
            }
 
        }
    }// build
 
    private static boolean trueCheck(int mM, int nN) {
 
        char wkC = workingBoard[mM][nN];
 
        if (wkC == '!')
            return false;
 
        boolean result = true;
 
        // 현재노드를기준으로 2*2가 성립하는지 확인
        for (int i = 0; i < 4; i++) {
 
            int nextM = mM + pointM[i];
            int nextN = nN + pointN[i];
 
            char nextC = workingBoard[nextM][nextN];
 
            if (wkC != nextC) {
                return false;
            }
        }
 
        return result;
    }
 
}// class
 

제출 결과

 

문제시 댓글 달아주시면 조치 및 수정하겠습니다.