프로그래머스: 프렌즈 4블럭

알고리즘 문제 해결 과정을 기록합니다

September 11, 2025 · 3 min read

#알고리즘 #문제해결

문제 개요 #

Source: 프로그래머스 링크
Difficulty: Lv 2
Key Concept: 구현

접근 방법 #

이 문제는 3단계로 나누었습니다. 2x2 블럭을 찾기, 해당 블럭을 삭제하기, 삭제된 블럭들 위에 있는 빈칸이 아닌 블럭들을 아래로 정렬하기 이 과정을 더 이상 2x2 블럭이 생기지 않을 때까지 반복하였습니다.

보드의 높이와 폭 모두 30 이하이므로 단순 반복문을 이용하여 빠르게 구현하는 것을 목표로 하였습니다.

시행착오 #

앞서 설명한 3단계 들은 빠르게 구현할 수 있었지만 블럭 찾기 부분에서 가장 중요한 조건을 놓쳤습니다. 알파벳이 아닌 ‘.‘으로 빈칸을 처리하였는데 빈 칸을 포함하여 다시 2x2 블럭을 찾는 로직을 구현하였습니다. 이로 인해 시간 초과 문제가 생겼었고 문제 푸는 시간이 예상보다 오래 걸렸었습니다.

해결 방법 #

#include <vector>
#include <string>
#include <algorithm>
#include <set>

#define Y first
#define X second

using std::set;
using std::string;
using std::pair;
using std::vector;

// 변수
int width,height,answer = 0;
vector<vector<char>> board;
set<pair<int, int>> pos;
// 함수

// 입력
void allocateCharVector(vector<string>& board){
    vector<vector<char>> b(height,vector<char>(width));
    for(int i = 0 ; i < height ; i++){
        for(int j = 0 ; j < width; j++){
            b[i][j] = board[i][j];
        }
    }
   	::board = b;
}

// 2x2 블록 탐색
bool retrieveSqaureBlock(){
    pos.clear();
    for(int i = 0 ; i < height- 1 ; i++){
        for(int j = 0 ; j < width - 1 ; j++){
            if( board[i][j] != '.' && // CHEKC: 가장 중요한 부분을 놓친거...
                board[i][j] == board[i][j+1] &&
               board[i][j] == board[i+1][j+1] &&
			   board[i][j] == board[i+1][j]){
               	pos.insert(std::make_pair(i,j)) ;
               	pos.insert(std::make_pair(i+1,j)) ;
               	pos.insert(std::make_pair(i,j+1)) ;
               	pos.insert(std::make_pair(i+1,j+1)) ;
            }
        }
    }
    return !pos.empty();
}

// 2x2 블록 제거 함수
void deleteSquareBlock(){
    for(const auto& p: pos){
        board[p.Y][p.X] = '.';
        answer++;
    }
}

void sortDownSwap(){
   for(int c = 0 ; c < width ; c++) {
       for(int r = height-1 ; r >= 0 ; --r){
           int temp_r = r;
           if(board[r][c] == '.') {continue;}
           while(temp_r < height - 1 &&
                board[temp_r+1][c] == '.'){
               std::swap(board[temp_r][c],board[temp_r+1][c]);
               temp_r++;
           }
       }
   }
}
// 아래로 정렬하는 함수(열을 기준으로 . 이 있다면 모두 내림)
void sortDown(){
   for(int c = 0 ; c < width ; c++) {
       int temp_height = height - 1;
       for(int r = height-1 ; r >= 0 ; --r){
           if(board[r][c] != '.'){
               board[temp_height][c] = board[r][c];
               if(temp_height  != r) board[r][c] ='.';
               --temp_height;
           }
       }
   }
}

// 블록 제거 후 아래로 정렬이 블록이 더이상 제거되지 않을 때 까지 반복
void iterateDeleation(){
    while(retrieveSqaureBlock()){
        deleteSquareBlock();
        sortDownSwap();
    }
}

int solution(int m, int n, vector<string> board) {
    height = m;
    width = n;

    allocateCharVector(board);
    iterateDeleation();
    return answer;
}

알고리즘 설명 #

2x2에서 조건문 중 정사각형이 모두 동일한 값뿐만 아니라 해당 칸이 빈칸이 아닌지를 먼저 검사하도록 하였습니다. 이에 따라 빈칸은 검사 대상에서 바로 제외했습니다. 또한 중복되어 여러 칸들이 2x2에 포함될 수 있기 때문에 set을 이용하여 중복이 포함되지 않도록 하였습니다.

set에 할당된 좌표값들을 바탕으로 board의 문자들을 ‘.‘으로 변경하여 빈칸으로 처리한 후 빈칸들에 대해서는 정렬하여 문자 칸과 칸 사이의 빈칸을 모두 제거하였습니다. 이때 swap을 이용해서 한 칸씩 모두 빈칸을 없애는 로직을 처음 생각하였고 해당 방법으로도 테스트는 통과할 수 있었으나 해당 방법을 최적화하고 싶어 투 포인터를 이용한 방법을 찾았습니다.

sortDown 함수가 해당 방법인데, 열의 가장 아래 칸부터 시작하여 빈칸이 안 나올 때까지는 r과 temp 값 모두 동일하게 올라가며 진행됩니다. 빈칸이 나왔을 때, r 값은 계속 올라가지만, temp 값은 가장 아래에 있는 빈칸을 가리키고 있습니다. 이후 빈칸이 아닌 값이 다시 나왔을 때 가장 아래에 있는 빈칸에 문자를 넣고, 원래 문자 자리에 빈칸을 넣어 둘을 변경합니다. 이후 temp 값은 바로 위에 있는 다시 갱신된 가장 아래의 빈칸을 다시 가리키고 있게 됩니다.

성능 분석 #

Time Complexity: $O((m\times n)^2)$

핵심 정리 #

문제 난도는 무난했지만, 특히 빈칸에 대해서 정렬하지 않는 조건을 붙이지 않았다는 사실이 너무 부끄러웠습니다. 문제의 난도와 상관없이 문제 풀이 시 꼼꼼하게 접근하는 자세의 필요성을 느꼈습니다. 또한 정렬에서의 효율성을 본 만큼 투 포인터에 대한 추가 학습을 진행하도록 하겠습니다.