프로그래머스 프렌즈4블록 - 자세한 풀이 (Java)

🧩 문제 정보

프렌즈4블록

• 문제: https://school.programmers.co.kr/learn/courses/30/lessons/17679
• 난이도: LV 2
• 유형: 구현, 자료구조

NewCodes의 풀이

• 스스로 풀었는가: O
• 다시 풀어볼 문제인가: X
• 풀이 시간: 45분 
• 제출 횟수: 1회
• 선택 언어: Java
• 풀이 환경: 프로그래머스 내 IDE

---

📝 풀이 정보

요구 사항 정리

1. 2 x 2 형태로 같은 블록이 4개 붙어 있을 경우 블록 사라짐
2. 블록 지워진 후에는 그 위에 있는 블록들이 떨어져서 빈 공간 채우기
3. 앞선 1~2의 시행에서 지운 블록이 있다면, 또 다시 1~2의 과정을 반복
4. 앞선 1~2의 시행에서 지워진 블록이 없다면, 게임 종료

 

풀이 설계

 : 풀이 설계에 있어 크게 세 메서드를 거치면 될 거라고 생각했습니다. 

1. 2 x 2 형태로 붙어있는 블록 완전탐색 -> boolean[][]에 지울 블록 true로 표시
2. boolean[][]을 바탕으로 true인 블록 지우기 & 떨어뜨리기
3. 1~2의 과정을 게임 종료 조건 만족 시까지 반복하기

 

 

통과한 풀이 (실전 풀이)

import java.util.*;

class Solution {
    public int solution(int m, int n, String[] board) {
        int answer = 0;
        
        // board를 2차원 배열로 변환
        char[][] boardArr = new char[m][n];
        for (int i = 0; i < m; i++) {
            char[] temp = board[i].toCharArray();
            
            for (int j = 0; j < n; j++) {
                boardArr[i][j] = temp[j];
            }
        }
        
        // 게임 시작
        boolean isGameActive = true;
        int removedBlocks = 0;
        while (isGameActive) {
            int beforeRemovedBlocks = removedBlocks;
            boolean[][] fourBlocks = new boolean[m][n];
                
            // 4블록인지 check
            for (int i = 0; i < m - 1; i++) {
                for (int j = 0; j < n - 1; j++) {
                    if (isFourBlock(boardArr, i, j)) {
                        fourBlocks[i][j] = true;
                        fourBlocks[i + 1][j] = true;
                        fourBlocks[i][j + 1] = true;
                        fourBlocks[i + 1][j + 1] = true;
                    }
                }
            }
            
            // 블록 지우기 & 떨어뜨리기
            for (int i = 0; i < n; i++) { // 열
                Deque<Character> dq = new ArrayDeque<>();
                
                for (int j = 0; j < m; j++) { // 행
                    if (!fourBlocks[j][i]) {
                        dq.offer(boardArr[j][i]);
                    }
                }
                
                // 순차적으로 떨어뜨리기
                int index = m - 1;
                while (!dq.isEmpty()) {
                    boardArr[index][i] = dq.pollLast();
                    index--;
                }
                
                // 위에 빈 블록 X로 표현
                for (int k = index; k >= 0; k--) {
                    boardArr[k][i] = 'X';
                    removedBlocks++;
                }
            }
            
            // System.out.println(Arrays.deepToString(boardArr));
            // break; // 임시!!!
            
            isGameActive = (beforeRemovedBlocks != removedBlocks);
        }
        
        return removedBlocks;
    }
    
    public static boolean isFourBlock(char[][] boardArr, int x, int y) {
        if (boardArr[x][y] == 'X') {
            return false;
        }
        
        if ((boardArr[x][y] == boardArr[x + 1][y]) 
            && (boardArr[x][y + 1] == boardArr[x + 1][y + 1])) {
            if (boardArr[x][y] == boardArr[x + 1][y + 1]) {
                return true;
            }
        }
        
        return false;
    }
}

 

 

풀이 시행 착오

 : 시행 착오는 한 번 있었습니다.

 

블록을 지운 후에 남은 블록을 떨어뜨리는 과정에서 있었습니다. 처음에는 블록을 지우자마자 블록을 떨어뜨리려 했지만, 이를 구현하기에는 다소 까다로움이 있었습니다. 코드가 복잡해져 관리하기도 어려울 것 같아 더 나은 방법이 있는지 중간에 다시 생각했습니다. 

 

다시 생각한 결과, 더 나은 방법을 찾을 수 있었습니다. 그 방법은 각 열에 대해 지워질 블록은 제외하고 남은 블록만 Deque에 담는 겁니다. 그리고 지워질 블록을 모두 체크했다면, Deque에 있던 걸 다시 꺼내면서 열을 순차적으로 재배치하는 것입니다. 

 

 

풀이 의도 설명

 : 아래 리팩토링한 코드를 기준으로 설명드리겠습니다. 해당 풀이에서의 포인트는 크게 두 가지입니다. 

1. boolean[][] blocksToDelete를 통해 지워질 블록 체크
2. Deque을 통해 각 열을 기준으로 블록 지우기 & 떨어뜨리기 수행 

blocksToDelete 2차원 배열을 통해 각 시행에서 지워질 블록의 위치에 대해 true로 저장했습니다. 

 

gameBoard에서 모든 블록에 대해 지워질 블록인지 아닌지를 체크했다면, 그 다음으로는 블록을 지우고 떨어뜨리는 동작을 수행합니다. 이때, 각 열을 기준으로 순회합니다. 블록을 지우고 나서 떨어뜨리는 동작을 수행하기 위해서는 수직을 기준으로 순회하는 것이 좋기 때문입니다. 

 

각 열에 대해 지워질 블록에 대해서는 Deque에 담지 않고, 지워지지 않는 블록에 대해서는 Deque에 담습니다. 해당 열의 모든 원소에 대해 이를 수행하고 나서는 열에서 가장 아랫 부분부터 블록을 배치합니다. 이렇게 배치하면, 자연스레 빈 공간이 사라지며 블록이 떨어진 것과 같은 동작을 수행합니다. 

 

 

리팩토링한 코드 (정돈된 풀이)

import java.util.*;

class Solution {
    private int m;
    private int n;
    
    public int solution(int m, int n, String[] board) {
        this.m = m;
        this.n = n;
        
        int totalRemovedBlocks = 0;
        boolean isGameActive = true;
        char[][] gameBoard = convert(board);
        
        while (isGameActive) {
            int beforeRemovedBlocks = totalRemovedBlocks;
            boolean[][] blocksToDelete = checkToDeleteBlocks(gameBoard);

            totalRemovedBlocks += removeBlocks(blocksToDelete, gameBoard);
            isGameActive = (beforeRemovedBlocks != totalRemovedBlocks);
        }
        
        return totalRemovedBlocks;
    }
    
    private char[][] convert(String[] board) {
        char[][] gameBoard = new char[m][n];
        for (int i = 0; i < m; i++) {
            char[] temp = board[i].toCharArray();
            
            for (int j = 0; j < n; j++) {
                gameBoard[i][j] = temp[j];
            }
        }
        
        return gameBoard;
    }
    
    private boolean[][] checkToDeleteBlocks(char[][] gameBoard) {
        boolean[][] blocksToDelete = new boolean[m][n];
        
        for (int i = 0; i < m - 1; i++) {
            for (int j = 0; j < n - 1; j++) {
                if (isSameBlock(gameBoard, i, j)) {
                    blocksToDelete[i][j] = true;
                    blocksToDelete[i + 1][j] = true;
                    blocksToDelete[i][j + 1] = true;
                    blocksToDelete[i + 1][j + 1] = true;
                }
            }
        }
        
        return blocksToDelete;
    }
    
    private boolean isSameBlock(char[][] gameBoard, int x, int y) {
        if (gameBoard[x][y] == 'X') { // 빈 블록인지 확인
            return false;
        }
        
        if ((gameBoard[x][y] == gameBoard[x + 1][y]) 
            && (gameBoard[x][y + 1] == gameBoard[x + 1][y + 1])
            && gameBoard[x][y] == gameBoard[x + 1][y + 1]) {
            return true;
        }
        
        return false;
    }
    
    private int removeBlocks(boolean[][] blocksToDelete, char[][] gameBoard) {
        int removedBlocks = 0;
        
        for (int i = 0; i < n; i++) { // 열
            Deque<Character> dq = new ArrayDeque<>(); // 한 열에서 삭제되지 않을 블록 저장

            for (int j = 0; j < m; j++) { // 행
                if (!blocksToDelete[j][i]) { 
                    dq.offer(gameBoard[j][i]);
                }
            }

            // 한 열에서 블록들 순차적으로 떨어뜨리기
            int index = m - 1;
            while (!dq.isEmpty()) {
                gameBoard[index][i] = dq.pollLast();
                index--;
            }

            // 한 열에서 위에 빈 블록 X로 표현
            for (int k = index; k >= 0; k--) {
                gameBoard[k][i] = 'X'; // 빈 블록을 X로 표현
                removedBlocks++;
            }
        }
        
        return removedBlocks;
    }
}

---

🎯 풀이 피드백

1. 초반에 설계 차분히 잘 한 것 같다!
2. 중간에 설계 잘못 한 부분 (블록 떨어뜨리기) 침착하게 잘 수정했다!
3. 주석으로 잘 구분하면서 풀었다! 이 덕에 큰 에러가 안 난 듯.
4. 메서드 작성 시 public static -> private
5. 전역 변수 작성 시 private static -> private