Programmers - 프렌즈4블록

---

title: Programmers - 프렌즈4블록
date: 2022-07-11
tags:

• Algorithm

---

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

문제 요약

m x n 타일에 프렌즈 블록이 주어진다. 같은 블록으로 2x2 정사각형을 이루면 해당 정사각형이 사라지며, 위에 있던 블록은 아래로 내려온다. 블록 배치에 따라 최종적으로 지워지는 블록의 수를 return한다.

문제 풀이

간단한 구현 문제이다.
2x2 구역을 생각하되, 좌상단이 프렌즈가 아니고 나머지 3군데에 같은 프렌즈가 있다면 지워질 대상이므로 queue에 넣는다.
동일한 위치의 프렌즈가 여러 구역에 해당될 수 있으므로, 지울 때 이전에 지워졌는지 확인을 해야한다.
블록이 지워짐에 따라 상단의 블록을 아래로 내려야 하는데, 정확히 없어진 위치에 집어넣는 작업은 많은 탐색을 필요로 한다.
간단하게 한 line을 기준으로 하단부터 프렌즈 블록의 경우 queue에 집어넣은 후, 하단부터 queue에 있는 블록을 배치해준다. queue가 비어있다면 그 위로는 블록이 없다는 의미이다.

프로그램

#include <string>
#include <vector>
#include <queue>
#include <utility>

using std :: string ;
using std :: vector ;
using std :: queue ;
using std :: pair ;
using std :: make_pair ;

int solution (int m , int n , vector < string > board )
{
    int answer = 0 ;
    bool bErase = true ;
    queue < pair < int , int > > qErase ;
    queue < char > qReplace ;



    while ( bErase )
    {
        bErase = false ;

        for ( int i = 0 ; i < m - 1 ; ++i )
        {
            for ( int j = 0 ; j < n - 1 ; ++j )
            {
                char cBlock = board [ i ] [ j ] ;

                if ( '-' == cBlock )
                    continue ;

                if ( ( cBlock == board [ i ] [ j + 1 ] ) && ( cBlock == board [ i + 1 ] [ j ] ) && ( cBlock == board [ i + 1 ] [ j + 1 ] ) )
                {
                    qErase.emplace ( make_pair ( i , j ) ) ;
                    qErase.emplace ( make_pair ( i , j + 1 ) ) ;
                    qErase.emplace ( make_pair ( i + 1 , j ) ) ;
                    qErase.emplace ( make_pair ( i + 1 , j + 1 ) ) ;

                    bErase = true ;
                }
            }
        }

        while ( ! qErase.empty () )
        {
            pair < int , int > pPoint = qErase.front () ;
            qErase.pop () ;

            if ( '-' != board [ pPoint.first ] [ pPoint.second ] )
            {
                board [ pPoint.first ] [ pPoint.second ] = '-' ;

                ++ answer ;
            }
        }
        if ( bErase )
        {
            for ( int j = 0 ; j < n ; ++j )
            {
                for ( int i = m - 1 ; i >= 0 ; --i )
                {
                    if ( '-' != board [ i ] [ j ] )
                        qReplace.emplace ( board [ i ] [ j ] ) ;
                }
                for ( int i = m - 1 ; i >= 0 ; --i )
                {
                    if ( qReplace.empty () )
                        board [ i ] [ j ] = '-' ;
                    else
                    {
                        board [ i ] [ j ] = qReplace.front () ;
                        qReplace.pop () ;
                    }
                }
            }
        }
    }


    return answer ;
}