[Java/자바] 프로그래머스 Lv2 - 프렌즈4블록

문제 설명

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록".
같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.

만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다.

같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.

블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.

만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.

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

TTTANT
RRFACC
RRRFCC
TRRRAA
TTMMMF
TMMTTJ

각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다

입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.

 

입력 형식

• 입력으로 판의 높이 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

 

---

Solution.java

먼저 여러 기능별로 메서드를 나누었습니다.

1. 동일한 블럭이 있는지 확인

2. 지운 블럭의 개수를 count

3. 지운 블럭의 자리를 위에 있는 블럭을 떨어트리는 함수

 

그리고 더 이상 동일한 블럭이 없을 때 까지 함수를 실행시키도록 while(true)문안에 넣어 실행시켰고

더 이상 동일한 블럭이 없어 count가 0일 때 while문을 종료시키도록 하였습니다.

 

테스트 케이스 5번 10번 실패 원인

잘못된 부분은 없다고 생각이 드는데 계속 실패를 해 테스트 케이스 5번 10번이 실패하는 원인을 알아보았습니다.

처음에는 "문자는 대문자 A에서 Z가 사용된다."이 부분을 A <= 문자 && 문자 <= Z 로 예외처리 해줘야 한다고 하더군요.

근데 이 부분은 수정해도 5번 10번은 그대로 실패였습니다. (이 부분은 예외처리를 안해도 통과되는거 보니 문제가 수정된거 같습니다.)

 

그 다음은 아래 행부터 탐색을 해야 5번 10번을 통과한다더군요

실패했을 당시 dropBlock() 메서드는 아래처럼 0행 0열 부터 떨어트릴 블럭이 있는지 탐색하였었습니다.

    private static void dropBlock(int m, int n) {
        for (int row = 0; row < m; row++) { ...
            for (int col = 0; col < n; col++) { ...

 

하지만 떨어트릴 블럭은 무조건 위에 있기 때문에 맨 아래의 행부터 탐색하도록 해야 시간적으로 효율적이여서 테스트가 통과되나 봅니다.

아래 처럼 dropBlock() 메서드를 수정하니 테스트 통과할 수 있었습니다.

    private static void dropBlock(int m, int n) {
        for (int row = m - 1; row >= 0; row--) { ...
            for (int col = 0; col < n; col++) { ...

 

정답 코드

public class 프렌즈4블록 {
    static char[][] blockMap;

    public static void main(String[] args) {
        System.out.println(solution(4, 5, new String[]{"CCBDE", "AAADE", "AAABF", "CCBBF"}));
    }

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

        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board[row].length(); col++) {
                blockMap[row][col] = board[row].charAt(col);
            }
        }

        while (true) {
            boolean[][] isSame = new boolean[m][n];
            checkBlock(m, n, isSame);
            int count = countBlock(m, n, isSame);
            if (count == 0) {
                break;
            }
            answer += count;

            dropBlock(m, n);
        }

        return answer;
    }

    private static void dropBlock(int m, int n) {
        // 밑에서부터 위로 탐색 (빈 블럭위에 떨어질 수 있는 블럭이 있는지 밑에서 부터 올라가면서 확인하기 때문)
        for (int row = m - 1; row >= 0; row--) {
            for (int col = 0; col < n; col++) {
                if (blockMap[row][col] != '-') {
                    continue;
                }
                if (blockMap[row][col] == '-') {
                    // '-' 위의 블록을 떨어트린다.
                    for (int k = row - 1; k >= 0; k--) { // 젤 위의 행까지 탐색
                        if (blockMap[k][col] != '-') {
                            blockMap[row][col] = blockMap[k][col];
                            blockMap[k][col] = '-';
                            break; // 다음 '-'를 찾으러 내부 반복문 종료
                        }
                    }
                }
            }
        }
    }

    public static void checkBlock(int m, int n, boolean[][] isSame) {
        for (int row = 0; row < m - 1; row++) {
            for (int col = 0; col < n - 1; col++) {
                char block = blockMap[row][col];
                // 아래 블럭, 옆 블럭, 대각선 블럭 총 4개의 블럭이 일치하다면 true
                if (blockMap[row + 1][col] == block && blockMap[row][col + 1] == block
                        && blockMap[row + 1][col + 1] == block) {
                    isSame[row + 1][col] = true;
                    isSame[row][col + 1] = true;
                    isSame[row + 1][col + 1] = true;
                    isSame[row][col] = true;
                }
            }
        }
    }

    public static int countBlock(int m, int n, boolean[][] isSame) {
        int count = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!isSame[i][j]) {
                    continue;
                }
                if (isSame[i][j] && blockMap[i][j] != '-') {
                    count++;
                    blockMap[i][j] = '-';
                }
            }
        }
        return count;
    }
}