catsridingCATSRIDING|OCEANWAVES
Challenges

프로그래머스 | Level 2 | [1차] 프렌즈4블록

jynn@catsriding.com
Aug 28, 2024
Published byJynn
999
프로그래머스 | Level 2 | [1차] 프렌즈4블록

Programmers | Level 2 | [1차] 프렌즈4블록

Problems

󰧭 Description

프렌즈4블록은 같은 모양의 블록이 2 × 2 형태로 인접해 있을 경우 사라지는 게임입니다. 주어진 m x n 크기의 보드에서 2 × 2로 배치된 블록들을 찾아 제거하고, 제거된 블록 위에 있던 블록들이 중력에 의해 아래로 떨어지며 빈 공간을 채웁니다. 같은 블록들이 계속해서 2 × 2로 배치되면, 이를 반복하여 더 이상 제거할 블록이 없을 때까지 진행됩니다. 최종적으로 제거된 블록의 개수를 계산하는 것이 목표입니다.

 Constraints

  • 보드의 높이 m과 폭 n은 2 ≤ m, n ≤ 30입니다.
  • 각 블록은 대문자 A에서 Z로 이루어져 있습니다.
  • 보드는 길이 n인 문자열 m개의 배열로 주어집니다.

󰦕 Examples

mnboardresult
45["CCBDE", "AAADE", "AAABF", "CCBBF"]14
66["TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"]15

Solutions

󰘦 Code

Solution.java
import java.util.*;

class Solution {
    public int solution(int m, int n, String[] board) {
        // 2차원 배열로 보드를 초기화
        char[][] grid = new char[m][n];
        for (int row = 0; row < board.length; row++) {
            grid[row] = board[row].toCharArray();
        }

        boolean hasMatches = true;
        int totalRemoved = 0;  // 제거된 블록의 총 개수

        // 블록이 사라질 때까지 반복
        while (hasMatches) {
            hasMatches = false;
            boolean[][] marked = new boolean[m][n];  // 제거할 블록을 마킹할 배열

            // 2×2 블록 탐색
            for (int row = 0; row < m - 1; row++) {
                for (int col = 0; col < n - 1; col++) {
                    char block = grid[row][col];
                    if (block == ' ') continue;  // 빈칸 건너뛰기
                    // 2×2 블록이 일치하는지 확인
                    if (block == grid[row][col + 1]
                        && block == grid[row + 1][col + 1]
                        && block == grid[row + 1][col]) {
                        // 제거될 블록 마킹
                        marked[row][col] = true;
                        marked[row][col + 1] = true;
                        marked[row + 1][col + 1] = true;
                        marked[row + 1][col] = true;
                        hasMatches = true;
                    }
                }
            }

            // 마킹된 블록 제거 및 카운트
            int roundRemoved = 0;
            for (int row = 0; row < m; row++) {
                for (int col = 0; col < n; col++) {
                    if (marked[row][col]) {
                        grid[row][col] = ' ';
                        roundRemoved++;
                    }
                }
            }

            // 제거된 블록이 없으면 종료
            if (roundRemoved == 0) break;

            totalRemoved += roundRemoved;  // 총 제거된 블록 수 누적

            // 빈 공간을 위의 블록으로 채우기
            for (int col = 0; col < n; col++) {
                for (int row = m - 1; row >= 0; row--) {
                    if (grid[row][col] == ' ') {  // 빈칸을 찾음
                        int rowAbove = row - 1;
                        // 위쪽에서 블록을 찾아 아래로 떨어뜨림
                        while (rowAbove >= 0 && grid[rowAbove][col] == ' ') {
                            rowAbove--;
                        }

                        if (rowAbove >= 0) {
                            grid[row][col] = grid[rowAbove][col];
                            grid[rowAbove][col] = ' ';
                        }
                    }
                }
            }
        }

        return totalRemoved;  // 총 제거된 블록 수 반환
    }
}

 Approach

이 문제는 시뮬레이션 문제로, 주어진 보드에서 블록들이 사라지는 과정을 시뮬레이션하여 최종적으로 몇 개의 블록이 제거되었는지 계산하는 문제입니다. 다음 단계로 문제를 해결합니다.

1. 문제 분석

이 문제는 주어진 m x n 크기의 보드에서 동일한 모양의 블록이 2 × 2 형태로 인접하면 해당 블록들을 제거하고, 제거된 블록 위에 있는 블록들이 아래로 떨어지는 과정을 반복해 최종적으로 제거된 블록의 총 개수를 구하는 시뮬레이션 문제입니다.

문제 해결의 핵심은 다음의 세 가지 주요 작업을 정확히 구현하는 데 있습니다:

  • 2 × 2 블록 탐색: 각 칸을 기준으로 오른쪽과 아래쪽에 인접한 세 칸이 같은 블록인지 확인하여 2 × 2 모양을 찾습니다. 이때 빈칸은 무시하며, 2 × 2 모양이 확인되면 해당 블록들을 제거 대상으로 마킹합니다.
  • 블록 제거 및 카운트: 마킹된 블록들은 제거되고 빈칸으로 대체됩니다. 이 과정에서 한 라운드에 제거된 블록의 개수를 카운트하여 누적합니다. 만약 한 라운드에서 제거된 블록이 없다면 더 이상 제거할 블록이 없다는 뜻이므로 루프를 종료합니다.
  • 빈 공간 채우기: 제거된 블록의 빈 공간은 위에 있는 블록들이 중력에 의해 떨어져 채워지도록 처리합니다. 각 열을 아래에서 위로 탐색하여 빈칸을 찾아 위쪽의 블록을 아래로 내려 채웁니다.

이 작업은 블록이 더 이상 제거되지 않을 때까지 반복되며, 최종적으로 제거된 블록의 총 개수를 반환합니다.

2. 보드 초기화

먼저 주어진 board 배열을 2차원 배열로 변환합니다. 각 문자열을 문자 배열로 변환하면 개별 블록을 처리하기가 훨씬 쉬워집니다.

Solution.java
// 2차원 배열로 변환
char[][] grid = new char[m][n];
for (int row = 0; row < board.length; row++) {
    grid[row] = board[row].toCharArray();  // 각 문자열을 문자 배열로 변환
}
3. 2 x 2 블록 탐색

보드에서 같은 모양의 블록들이 2 × 2로 배열된 부분을 찾아 제거할 블록들을 마킹합니다. 이 탐색은 보드의 각 칸을 기준으로, 해당 칸이 속한 2 × 2 구역이 같은 블록으로 이루어져 있는지 확인하는 방식으로 이루어집니다. 빈칸은 탐색에서 제외하고, 같은 모양의 블록이 발견되면 해당 블록들을 마킹하여 나중에 제거할 수 있도록 합니다.

탐색은 다음과 같은 순서로 진행됩니다:

  1. 보드의 각 칸을 순차적으로 탐색합니다.
  2. 현재 칸이 빈칸이 아니면, 현재 칸을 기준으로 오른쪽과 아래로 인접한 칸들이 동일한 블록으로 이루어져 있는지 확인합니다.
  3. 만약 2 × 2 블록이 확인되면, 해당 블록들을 제거 대상으로 마킹합니다.
  4. 마킹된 블록은 이후 단계에서 실제로 제거됩니다.

보드의 마지막 행과 열에서는 2 × 2 블록을 만들 수 없기 때문에 탐색 범위를 m - 1 × n - 1로 제한합니다.

Solution.java
boolean[][] marked = new boolean[m][n];  // 제거할 블록을 마킹할 배열
            
for (int row = 0; row < m - 1; row++) {  // 마지막 행은 탐색하지 않음
    for (int col = 0; col < n - 1; col++) {  // 마지막 열도 탐색하지 않음
        char block = grid[row][col];
        
        // 빈칸은 건너뛰기
        if (block == ' ') continue;

        // 현재 칸을 기준으로 오른쪽과 아래쪽 칸들이 같은 블록인지 확인
        if (block == grid[row][col + 1]         // 오른쪽 블록
            && block == grid[row + 1][col + 1]  // 아래 오른쪽 블록
            && block == grid[row + 1][col]) {   // 아래 블록

            // 2 x 2 블록이 발견되면 해당 블록들을 제거 대상으로 마킹
            marked[row][col] = true;
            marked[row][col + 1] = true;
            marked[row + 1][col + 1] = true;
            marked[row + 1][col] = true;

            // 2 x 2 블록이 하나라도 발견된 경우, 반복을 계속할 수 있도록 플래그 설정
            hasMatches = true;
        }
    }
}

이 과정은 전체 보드를 순차적으로 탐색하면서 이루어지며, 더 이상 제거할 블록이 없을 때까지 반복됩니다.

4. 블록 제거 및 카운트

마킹된 블록들을 모두 제거하고 해당 위치를 빈칸으로 바꿉니다. 이 과정에서 제거된 블록의 개수를 카운트합니다. 만약 한 라운드에서 제거된 블록이 없다면, 더 이상 처리할 블록이 없다는 의미로 루프를 종료합니다. 해당 라운드에서 제거된 블록이 있다면 제거된 블록 수 만큼 누적합니다.

Solution.java
int roundRemoved = 0;
for (int row = 0; row < m; row++) {
    for (int col = 0; col < n; col++) {
        if (marked[row][col]) {
            grid[row][col] = ' ';  // 블록 제거
            roundRemoved++;
        }
    }
}
// 블록이 제거되지 않았다면 루프 종료
if (roundRemoved == 0) break;

// 총 제거된 블록 수 누적
totalRemoved += roundRemoved;
5. 블록 아래로 떨어뜨리기

블록들이 제거된 후, 빈칸이 생기면 그 위에 있던 블록들이 아래로 떨어져야 합니다. 이 작업은 각 열을 하나씩 검사하여, 빈칸이 발견되면 해당 열 위쪽에 남아있는 블록들을 아래로 이동시키는 방식으로 진행됩니다. 이를 통해 위의 블록들이 자연스럽게 빈칸을 채우게 됩니다.

구체적인 과정은 다음과 같습니다:

  1. 각 열 별로 처리: 각 열의 최하단에서부터 위쪽으로 빈칸을 찾아갑니다. 빈칸이 발견되면 그 위쪽에 있는 블록을 찾아 그 블록을 빈칸으로 떨어뜨립니다. 이때, 위쪽으로 올라가며 첫 번째로 만나는 블록을 떨어뜨리고, 떨어진 블록의 자리는 다시 빈칸으로 만듭니다.
  2. 빈칸 확인 및 블록 이동: 빈칸을 만나면 위쪽으로 올라가면서 블록을 찾아 아래로 떨어뜨리는 작업을 반복합니다. 만약 블록을 찾지 못했다면, 해당 열에는 더 이상 블록이 없다는 의미이므로 더 이상 탐색하지 않습니다.
  3. 반복 처리: 각 열마다 이 과정을 반복하여 빈칸이 남지 않도록 합니다. 이 작업은 모든 열에 대해 적용되며, 더 이상 위에서 떨어질 블록이 없으면 빈칸이 그대로 남게 됩니다.
Solution.java
for (int col = 0; col < n; col++) {  // 모든 열을 검사
    for (int row = m - 1; row >= 0; row--) {  // 해당 열의 가장 아래에서 위로 탐색
        if (grid[row][col] == ' ') {  // 빈칸을 찾음
            int rowAbove = row - 1;  // 빈칸 위쪽의 블록을 찾기 시작
            // 위쪽에서 블록을 찾을 때까지 탐색
            while (rowAbove >= 0 && grid[rowAbove][col] == ' ') {
                rowAbove--;  // 위쪽으로 계속 이동하며 블록을 찾음
            }
            // 위쪽에 블록이 있으면 해당 블록을 아래로 떨어뜨림
            if (rowAbove >= 0) {
                grid[row][col] = grid[rowAbove][col];  // 블록을 빈칸으로 이동
                grid[rowAbove][col] = ' ';  // 위쪽 블록 자리는 빈칸으로 만듦
            }
        }
    }
}
  • 각 열에서 가장 아래쪽 행부터 위쪽으로 올라가면서 빈칸을 찾습니다. 중력의 영향으로 블록이 아래로 떨어져야 하기 때문에, 아래쪽부터 탐색하는 것이 적절합니다.
  • 빈칸을 발견하면 그 위쪽에서 블록을 찾아 내려보내야 합니다. rowAbove를 사용해 위쪽으로 올라가면서 블록이 있는 위치를 찾고, 해당 블록을 빈칸으로 이동시킵니다. 만약 블록을 찾지 못했다면, 그 열에 더 이상 떨어질 블록이 없다는 뜻입니다.
  • 블록을 아래로 떨어뜨리면, 원래 블록이 있던 자리 grid[rowAbove][col]는 빈칸으로 처리됩니다. 이를 통해 연쇄적으로 블록들이 아래로 떨어지면서 빈칸이 점점 채워지게 됩니다.

이 과정을 통해 빈칸이 채워지면 다음 라운드에서 다시 2 × 2 블록 탐색을 시작하게 되며, 더 이상 제거할 블록이 없을 때까지 이 과정을 반복합니다.

6. 반복 및 종료 조건

이 과정을 더 이상 블록이 사라지지 않을 때까지 반복합니다. 더 이상 제거할 블록이 없다면, 루프를 종료하고 최종적으로 제거된 블록의 총 개수를 반환합니다.

Solution.java
while (hasMatches) {...}

// 총 제거된 블록 수 반환
return totalRemoved;

󰄉 Complexity

  • ⏳ TC: O(n)
  • 💾 SC: O(n)

이 알고리즘은 보드의 모든 칸을 순차적으로 탐색하고 블록을 제거하며 빈 공간을 채우는 작업을 반복하기 때문에 시간 복잡도는 O(n)입니다. 여기서 n은 보드의 전체 칸 수를 의미합니다. 또한, 보드를 저장하는 배열과 제거 여부를 마킹하는 배열 역시 n 크기를 차지하므로, 공간 복잡도도 O(n)입니다. 이 문제는 블록을 탐색하고 제거하며 빈 공간을 채우는 시뮬레이션 문제로, 효율적인 구현을 통해 안정적인 결과를 도출할 수 있습니다.

  • Algorithm
  • Simulation