프렌즈4블록

문제

카카오 프렌즈 캐릭터 블록이 2x2 형태로 4개가 모이면 지워지는 게임입니다. 같은 모양의 카카오 프렌즈 블록 2x2가 모여 블록이 지워지면, 위에 있는 블록들이 중력에 의해 빈자리를 채우며 아래로 떨어집니다. 떨어지고 난 후 다시 2x2 모양이 모이면 또 지워지며, 이 과정은 더 이상 지워질 블록이 없을 때까지 반복됩니다. 입력으로 판의 높이 m, 폭 n, 그리고 판의 배치 정보 board가 주어질 때, 지워지는 블록의 총 개수를 구하는 프로그램을 작성하는 문제입니다.

• 입력: 높이 m (2 ≦ m ≦ 30), 폭 n (2 ≦ n ≦ 30), 판의 배치 정보 board (길이 n인 문자열 m개의 배열)
• 출력: 지워지는 블록의 총 개수를 반환합니다.

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

풀이: 2x2 블록 탐색과 중력(떨어짐) 시뮬레이션

주어진 규칙에 따라 블록을 찾아 지우고, 빈 공간을 메우기 위해 블록을 아래로 떨어뜨리는 과정을 무한 루프(while(true)) 안에서 반복하는 시뮬레이션 방식입니다.

• 초기화: 문자열 다루기를 용이하게 하기 위해 1차원 문자열 배열인 board를 2차원 char 배열 a로 변환합니다.
• 블록 탐색: m-1, n-1까지 2중 반복문을 돌며 현재 위치 (i, j)를 기준으로 우측, 하단, 우측 하단 대각선 칸이 모두 같은 캐릭터인지 확인합니다. 빈칸(' ')이 아니면서 4칸이 모두 일치한다면, 지워질 블록임을 check 배열에 true로 표시합니다. (겹치는 블록이 있을 수 있으므로 탐색 중에는 바로 지우지 않고 표시만 해둡니다.)
• 블록 떨어뜨리기: 새로운 임시 배열 tmp를 만들어 모두 빈칸으로 초기화합니다. 각 열(i)마다 맨 아래 행부터 위로 올라가며 블록을 검사합니다.
  • 조건문 if (check[j][i] || a[j][i] == ' ') continue;를 통해, 지워질 예정인 블록이거나 이미 빈칸인 경우에는 임시 배열로의 복사를 건너뜁니다.
  • 조건에 걸리지 않은 유효한 블록만 tmp의 밑바닥 인덱스(idx)부터 차곡차곡 쌓아 올립니다.
• 종료 및 정답 계산: 한 번의 루프 동안 지워진 블록이 하나도 없다면(flag가 true 유지), 더 이상 진행할 수 없으므로 루프를 탈출합니다. 마지막으로 전체 원본 배열에서 빈칸(' ')의 개수를 세어 지워진 총 블록의 개수로 반환합니다.

코드

import java.util.*;

class Solution {
    public int solution(int m, int n, String[] board) {
        char[][] a = new char[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                a[i][j] = board[i].charAt(j);
            }
        }
        
        while(true) {
            boolean flag = true;
            boolean[][] check = new boolean[m][n];
            
            // 1. 2x2 블록 찾기
            for (int i = 0; i < m - 1; i++) {
                for (int j = 0; j < n - 1; j++) {
                    // 빈칸이 아니고 4칸이 모두 같은 모양인지 확인
                    if (a[i][j] != ' ' && 
                        a[i][j] == a[i][j + 1] && 
                        a[i][j] == a[i + 1][j] && 
                        a[i][j] == a[i + 1][ j + 1]) {
                        
                        flag = false; // 지울 블록이 하나라도 존재함
                        check[i][j] = check[i + 1][j] = check[i][j + 1] = check[i + 1][j + 1] = true;
                    }
                }
            }
            
            // 더 이상 지워질 블록이 없으면 루프 종료
            if (flag) break;
            
            char[][] tmp = new char[m][n];
            for (int i = 0; i < m; i++) 
                Arrays.fill(tmp[i], ' ');
            
            // 2. 블록 아래로 떨어뜨리기
            for (int i = 0; i < n; i++) {
                int idx = m - 1;
                for (int j = m - 1; j >= 0; j--) {
                    // 지워질 블록이거나 기존 빈칸이면 복사하지 않고 건너뜀
                    if (check[j][i] || a[j][i] == ' ') continue;
                    
                    tmp[idx][i] = a[j][i];
                    idx--;
                }
            }
            
            // 3. 임시 배열의 결과를 원본 배열에 덮어쓰기
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    a[i][j] = tmp[i][j];
                }
            }
        }
        
        // 4. 지워진 빈칸(' ') 개수 세기
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (a[i][j] == ' ') ans++;
            }
        }
        
        return ans;
    }
}

알고리즘 분류

구현 (Implementation), 시뮬레이션 (Simulation)