Programmers | Level 2 | [1차] 프렌즈4블록
![Programmers | Level 2 | [1차] 프렌즈4블록](/_next/image?url=https%3A%2F%2Fcatsriding.s3.ap-northeast-2.amazonaws.com%2Fposts%2Fthumbnails%2F2024-08-28%2F9158b413-27c9-4ac5-8b70-691b5832ddf3.png&w=1920&q=75)
Programmers | Level 2 | [1차] 프렌즈4블록
Problems
- 📘 Src: Programmers
- 🗂️ Cat: Simulation
Description
프렌즈4블록은 같은 모양의 블록이 2 × 2 형태로 인접해 있을 경우 사라지는 게임입니다. 주어진 m x n 크기의 보드에서 2 × 2로 배치된 블록들을 찾아 제거하고, 제거된 블록 위에 있던 블록들이 중력에 의해 아래로 떨어지며 빈 공간을 채웁니다. 같은 블록들이 계속해서 2 × 2로 배치되면, 이를 반복하여 더 이상 제거할 블록이 없을 때까지 진행됩니다. 최종적으로 제거된 블록의 개수를 계산하는 것이 목표입니다.
Constraints
- 보드의 높이
m과 폭n은 2 ≤m,n≤ 30입니다. - 각 블록은 대문자 A에서 Z로 이루어져 있습니다.
- 보드는 길이
n인 문자열m개의 배열로 주어집니다.
Examples
| m | n | board | result |
|---|---|---|---|
| 4 | 5 | ["CCBDE", "AAADE", "AAABF", "CCBBF"] | 14 |
| 6 | 6 | ["TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"] | 15 |
Solutions
Code
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차원 배열로 변환합니다. 각 문자열을 문자 배열로 변환하면 개별 블록을 처리하기가 훨씬 쉬워집니다.
// 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 구역이 같은 블록으로 이루어져 있는지 확인하는 방식으로 이루어집니다. 빈칸은 탐색에서 제외하고, 같은 모양의 블록이 발견되면 해당 블록들을 마킹하여 나중에 제거할 수 있도록 합니다.
탐색은 다음과 같은 순서로 진행됩니다:
- 보드의 각 칸을 순차적으로 탐색합니다.
- 현재 칸이 빈칸이 아니면, 현재 칸을 기준으로 오른쪽과 아래로 인접한 칸들이 동일한 블록으로 이루어져 있는지 확인합니다.
- 만약 2 × 2 블록이 확인되면, 해당 블록들을 제거 대상으로 마킹합니다.
- 마킹된 블록은 이후 단계에서 실제로 제거됩니다.
보드의 마지막 행과 열에서는 2 × 2 블록을 만들 수 없기 때문에 탐색 범위를 m - 1 × n - 1로 제한합니다.
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. 블록 제거 및 카운트
마킹된 블록들을 모두 제거하고 해당 위치를 빈칸으로 바꿉니다. 이 과정에서 제거된 블록의 개수를 카운트합니다. 만약 한 라운드에서 제거된 블록이 없다면, 더 이상 처리할 블록이 없다는 의미로 루프를 종료합니다. 해당 라운드에서 제거된 블록이 있다면 제거된 블록 수 만큼 누적합니다.
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. 블록 아래로 떨어뜨리기
블록들이 제거된 후, 빈칸이 생기면 그 위에 있던 블록들이 아래로 떨어져야 합니다. 이 작업은 각 열을 하나씩 검사하여, 빈칸이 발견되면 해당 열 위쪽에 남아있는 블록들을 아래로 이동시키는 방식으로 진행됩니다. 이를 통해 위의 블록들이 자연스럽게 빈칸을 채우게 됩니다.
구체적인 과정은 다음과 같습니다:
- 각 열 별로 처리: 각 열의 최하단에서부터 위쪽으로 빈칸을 찾아갑니다. 빈칸이 발견되면 그 위쪽에 있는 블록을 찾아 그 블록을 빈칸으로 떨어뜨립니다. 이때, 위쪽으로 올라가며 첫 번째로 만나는 블록을 떨어뜨리고, 떨어진 블록의 자리는 다시 빈칸으로 만듭니다.
- 빈칸 확인 및 블록 이동: 빈칸을 만나면 위쪽으로 올라가면서 블록을 찾아 아래로 떨어뜨리는 작업을 반복합니다. 만약 블록을 찾지 못했다면, 해당 열에는 더 이상 블록이 없다는 의미이므로 더 이상 탐색하지 않습니다.
- 반복 처리: 각 열마다 이 과정을 반복하여 빈칸이 남지 않도록 합니다. 이 작업은 모든 열에 대해 적용되며, 더 이상 위에서 떨어질 블록이 없으면 빈칸이 그대로 남게 됩니다.
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. 반복 및 종료 조건
이 과정을 더 이상 블록이 사라지지 않을 때까지 반복합니다. 더 이상 제거할 블록이 없다면, 루프를 종료하고 최종적으로 제거된 블록의 총 개수를 반환합니다.
while (hasMatches) {...}
// 총 제거된 블록 수 반환
return totalRemoved;
Complexity
- ⏳ TC: O(n)
- 💾 SC: O(n)
이 알고리즘은 보드의 모든 칸을 순차적으로 탐색하고 블록을 제거하며 빈 공간을 채우는 작업을 반복하기 때문에 시간 복잡도는 O(n)입니다. 여기서 n은 보드의 전체 칸 수를 의미합니다. 또한, 보드를 저장하는 배열과 제거 여부를 마킹하는 배열 역시 n 크기를 차지하므로, 공간 복잡도도 O(n)입니다. 이 문제는 블록을 탐색하고 제거하며 빈 공간을 채우는 시뮬레이션 문제로, 효율적인 구현을 통해 안정적인 결과를 도출할 수 있습니다.
- Algorithm
- Simulation